Problem: 20. 有效的括号
思路
Mryan2005，觉得要先将不相干的先入栈，然后，当遇到相关的括号时，出栈。
解题方法
有思路可得
复杂度
时间复杂度:
O(n)
空间复杂度:
O(n)
Code
[]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| typedef struct stackNode {
char data;
struct stackNode *next;
} stackNode, *Stack;
void Push(Stack *S, char data) {
stackNode *p = (stackNode*)malloc(sizeof(stackNode));
p->data = data;
p->next = *S;
*S = p;
}
char GetHead(Stack S) {return S? S->data: 0;}
char Pop(Stack *S) {
char data;
stackNode *p = *S;
data = p->data;
*S = (*S)->next;
free(p);
return data;
}
bool isValid(char* s) {
Stack S = NULL;
for(char *p = s, c; *p != 0; p++) {
if(S) {
c = GetHead(S);
if(c == '(' && *p == ')') Pop(&S);
else if(c == '[' && *p == ']') Pop(&S);
else if(c == '{' && *p == '}') Pop(&S);
else Push(&S, *p);
} else Push(&S, *p);
}
if(!S) return true;
else return false;
}
|
