32. Longest Valid Parentheses
Given a string containing just the characters
'('
and ')'
, find the length of the longest valid (well-formed) parentheses substring.
For
"(()"
, the longest valid parentheses substring is "()"
, which has length = 2.
Another example is
")()())"
, where the longest valid parentheses substring is "()()"
, which has length = 4.
題意:
給定字元串(字元串隻包括 '(' 和 ')' 元素)。查找最長的有效字串,即 '(' 和 ')' 比對的最長字串。
思路:
1)建立棧,碰到比對的括号時,彈出棧頂元素;否則,。
2)建立數組,當出棧動作發生時,把到目前為止的入棧次數與出棧次數的內插補點存入數組中。
3)數組處理。擷取最長字串。
A)字元串模式
)) (()) ) ((())) 對應數組為:3 2 5 4 3
B)字元串模式
)) ()() ) ()()() 對應數組為:2 2 3 3 3
C)字元串模式
)) () ) ()((())) 對應數組為:2 3 5 4 3
D)字元串模式
)) (()) ) (())() 對應數組為:3 2 4 3 3
由上可知:
模式比對基本就隻有
1,嵌套(())
2,平級()()
第一種方式的數組會出現遞減方式,第二種方式的數組元素會出現保持不變的。
一旦出現不比對的,那麼隻有push動作存在,遇到pop時中間push和pop的差肯定是增漲的。可是如果中間都是比對的,那麼最終push和pop的差不會漲。
擷取最長字串的方法:
擷取遞減序列,紀錄遞減序列長度,并紀錄遞減序列開始的首元素和尾元素。從紀錄的首元素開始往前查找,直到遇到的元素小于紀錄的尾元素,記前驅長度。
遞減序列長度+前驅長度 = 字串長度。
struct stack
{
char word;
struct stack *next;
};
struct stack
*push(struct stack *head, char word)
{
struct stack *node = (struct stack *)malloc(sizeof(struct stack));
if ( !node )
{
printf("create node error\n");
return head;
}
node->word = word;
if ( !head )
{
node->next = NULL;
head = node;
}
else
{
node->next = head;
}
return node;
}
struct stack
*pop(struct stack *head)
{
if ( !head )
{
return head;
}
struct stack *del = head;
head = head->next;
free(del);
return head;
}
char
top(struct stack *head)
{
if ( !head )
{
return 0;
}
return head->word;
}
void
stackFree(struct stack *head)
{
if ( !head )
{
return;
}
struct stack *del = NULL;
while ( head )
{
del = head;
head = head->next;
free(del);
}
}
int
longestValidParentheses(char* s)
{
if ( !s )
{
return 0;
}
int size = strlen(s) / 2 + 1;
int sub[size];
int index = 0;
struct stack *head = NULL;
int pushNum = 0;
int popNum = 0;
int flag = 0;
for ( ; *s; s++ )
{
if ( *s == '(' )
{
head = push(head, *s);
pushNum += 1;
flag = 0;
}
else if ( *s == ')' )
{
if ( top(head) == '(' )
{
head = pop(head);
popNum += 1;
flag = 1;
}
else
{
head = push(head, *s);
pushNum += 1;
flag = 0;
}
}
if ( flag == 1 )
{
sub[index] = pushNum - popNum;
index += 1;
}
}
stackFree(head);
if ( index == 1 )
{
return index * 2;
}
int length = 0;
int maxLen = 0;
int cnt = 0;
int min = 0;
for ( cnt = 0; cnt < index - 1; cnt++ )
{
length = 0;
min = -1;
while ( (cnt + 1 + length) < index && sub[cnt + length] >= sub[cnt + 1 + length] )
{
length += 1;
}
while ( (cnt - 1 - min) >= 0 && sub[cnt - 1 - min] >= sub[cnt + length] )
{
min += 1;
}
cnt = cnt + length;
length = length + 1 + min;
if ( length > maxLen )
{
maxLen = length;
}
}
return maxLen * 2;
}