20. 有效的括号

给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = “()”
输出:true
示例 2:

输入:s = “()[]{}”
输出:true
示例 3:

输入:s = “(]”
输出:false

提示:

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

方法一:
class Solution {
    public boolean isValid(String s) {
      //s.replace(a,b) 把a替换为b[字符串型]
      while(true){
            int l = s.length();
            s=s.replace("()","");
            s=s.replace("{}","");
            s=s.replace("[]","");
            if(s.length()== l){return l==0;}
        }
    }
}

知识点:
1.s.replace语法
             public String replace(char searchChar, char newChar)    

2."字符串" ;'字符' ; "abc" => abc\0  ; 'a' = a

3.数组 arr.length
  字符串 s.length()

4.最后一个if很精妙,返回值== ,表判断

 

方法二:
//定义结构体
typedef struct LNode {
    char data;
    struct LNode* next;
}LNode;

bool IsEmpty(LNode *stk) {             // 判断栈是否为空
    return (stk == NULL);
}

void push(LNode **stk, char ch) {      // 压栈
    LNode *p = (LNode*)malloc(sizeof(LNode));
    p->data = ch;
    p->next = *stk;
    *stk = p;
}

char pop(LNode **stk) {                // 弹栈
    LNode *p = *stk;
    char t = p->data; 
    *stk = p->next;
    free(p);
    return t;
}

bool match(char s1, char s2) {
    if (s1 == '(' && s2 == ')') return true;
    else if (s1 == '[' && s2 == ']') return true;
    else if (s1 == '{' && s2 == '}') return true;
    else return false;
}

bool isValid(char * s){
    LNode *stk = NULL;                 // 栈顶指针
    bool flag = true; 
    int index = 0, l = strlen(s);
    while (index < l && flag) {
        char elem = *(s + index);
        if (elem == '(' || elem == '[' || elem == '{') push(&stk, elem);
        else {
            if (IsEmpty(stk)) flag = false;
            else {
                char top = pop(&stk);
                if (!match(top, elem)) flag = false;
            }
        }
        index++;
    }
    if (IsEmpty(stk) && flag) return true;
    else return false;
}

知识点:
用到栈的先进后出,大家可以了解一下,C的知识快忘了,有兴趣可以自行了解

Chttps://leetcode.cn/problems/valid-parentheses