20. 有效的括号

题目链接：https://leetcode-cn.com/problems/valid-parentheses/

Cpp实现

用栈存入的时候判断ascii码差值，决定是否pop前一个符号。
耗时0ms

代码

class Solution {
public:
    bool isValid(string s) {
        if (s.length()%2 == 1){
            return false;
        }
        stack<char> st;
        for (int i = 0; i < s.length(); ++i) {
            //一开始为空，压入一个符号后，要比较的是下一个符号
            if (st.empty()){
                st.push(s[i]);
                i++;
            }
            char t = st.top();
            if (s[i] - t == 1 || s[i] - t == 2){
                st.pop();
            }else{
                st.push(s[i]);
            }
        }
        return st.empty();
    }
};

swift实现1

执行用时：4 ms, 在所有 Swift 提交中击败了87.89%的用户
内存消耗：13.9 MB, 在所有 Swift 提交中击败了81.71%的用户

class Solution {
    func isValid(_ s: String) -> Bool {
        var stack: [Character] = []
        for i in s {
            if stack.isEmpty ||
                       i == "(" ||
                       i == "[" ||
                       i == "{"{
                stack.append(i)
            }else{
                let tmp = stack.last
                if tmp == "(" && i == ")" ||
                           tmp == "[" && i == "]" ||
                           tmp == "{" && i == "}"
                {
                    stack.removeLast()
                }else{
                    return false
                }
            }
        }
        if stack.isEmpty {
            return true
        }
        return false
    }
}

swift实现2

swift 用数组模拟栈，switch 和 if-else实现

执行用时：0 ms, 在所有 Swift 提交中击败了100.00%的用户
内存消耗：14 MB, 在所有 Swift 提交中击败了51.07%的用户

代码

class Solution {
    func isValid(_ s: String) -> Bool {
        if s.count % 2 == 1 {
            return false
        }
        var stack: [Character] = []
        for i in s {
            if stack.isEmpty {
                stack.append(i)
            }else{
                switch i {
                case "(", "[", "{":
                    stack.append(i)
                case ")":
                    if stack.last == "(" {
                        stack.removeLast()
                    }else {
                        return false
                    }
                case "]":
                    if stack.last == "[" {
                        stack.removeLast()
                    }else {
                        return false
                    }
                case "}":
                    if stack.last == "{" {
                        stack.removeLast()
                    }else {
                        return false
                    }
                default:
                    return false
                }
            }
        }
        if stack.isEmpty {
            return true
        }
        return false
    }
}

测试用例

“(])”
“)”
“)(){}”
“()”
“()[]{}”
“(]”
“([)]”
“{[]}”
“[“
“((“