描述

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

思路

这里我有两个思路，思路一很快就实现了，并且效果还可以，思路二，在实现的时候出了一些问题。花费了不少时间，还是没有解决，为了刷题，先放下。 思路一：利用栈的思想。 思路二：想要利用hash表来减少判断的过程。不过出现了一下问题，没有跑起来。

代码

思路一：

class Solution { public: bool isValid(string s) { int s_size = s.size(); vector<char> chsVec; chsVec.push_back('a'); char temp; bool chs_map[128] = {false}; chs_map['('] = true; chs_map['{'] = true; chs_map['['] = true; chs_map[')'] = true; chs_map['}'] = true; chs_map[']'] = true; for(int i = 0; i < s_size; i++){ temp = s[i]; if(chs_map[temp]){ switch(temp){ case '(':{ chsVec.push_back(temp); break; } case '{':{ chsVec.push_back(temp); break; } case '[':{ chsVec.push_back(temp); break; } case ')':{ if(chsVec.back() == '('){ chsVec.pop_back(); } else{ return false; } break; } case '}':{ if(chsVec.back() == '{'){ chsVec.pop_back(); } else{ return false; } break; } case ']':{ if(chsVec.back() == '['){ chsVec.pop_back(); } else{ return false; } break; } } } } if(chsVec.size() == 1){ return true; } else{ return false; } } };

思路二：

class Solution { public: bool isValid(string s) { int s_size = s.size(); char chs_vec[s_size+1]; int index = 0; char temp; bool chs_map[128] = {false}; chs_map['('] = true; chs_map['{'] = true; chs_map['['] = true; chs_map[')'] = true; chs_map['}'] = true; chs_map[']'] = true; bool chs_left[128] = {false}; chs_map['('] = true; chs_map['{'] = true; chs_map['['] = true; char chs_right[128]; chs_map[')'] = '('; chs_map['}'] = '{'; chs_map[']'] = '['; for(int i = 0; i < s_size; i++){ temp = s[i]; if(chs_map[temp]){ cout << temp << endl; cout << chs_left[temp] << endl; if(chs_left[temp]){ index++; chs_vec[index] = temp; } else{ cout << index << endl; cout << temp << endl; if(chs_vec[index] == chs_right[temp]){ index--; cout << index; } else{ return false; } } } } cout << 'over' << endl; if(index == 0){ return true; } else{ return false; } } };

结果

他山之玉

C++ O(n) solutioin

int getV(char c) { if (c == '(') return 1; else if (c == ')') return -1; else if (c == '[') return 2; else if (c == ']') return -2; else if (c == '{') return 3; else if (c == '}') return -3; else return 0; } bool isValid(string s) { stack<int> st; for (int i = 0; i < s.size(); i++) { int v = getV(s[i]); if (v < 0) { if (st.empty()) return false; if (st.top() + v) return false; st.pop(); } else { st.push(v); } } return st.empty(); }

这个思路将字符的比对转换成加减。

Java O(n) solution

public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); for (char c : s.toCharArray()) { if (c == '(') stack.push(')'); else if (c == '{') stack.push('}'); else if (c == '[') stack.push(']'); else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty(); }

恩，这个更加简洁，值得借鉴。

python O(n) solution

class Solution: # @return a boolean def isValid(self, s): stack = [] dict = {"]":"[", "}":"{", ")":"("} for char in s: if char in dict.values(): stack.append(char) elif char in dict.keys(): if stack == [] or dict[char] != stack.pop(): return False else: return False return stack == []