LeetCode #20. Valid Parentheses プログラミング練習
問題:
難易度: easy
入力: String
目的: 入力された括弧が有効かどうかを判断せよ
出力: boolean
入力されるのは'(', ')', '{', '}', '[' と ']'の組み合わせです。
入力された括弧群が有効かどうかを判断します。
例えば((())), [()]等でしたら有効で、
[(])でしたら無効になります。
注意すべき事:
- 括弧の左の部分が右の部分より多ければ無効
- 括弧の中に閉じていない括弧があっても無効
- 括弧がすべて閉じていない場合もある
以下回答です。
class Solution { public boolean isValid(String s) { Stack<Character> st = new Stack<Character>(); int len = s.length(); Map<Character, Character> map = new HashMap<Character, Character>(); map.put('(',')'); map.put('[',']'); map.put('{','}'); for(int i=0; i<len; i++) { Character n = s.charAt(i); switch(n) { case '{': case '(': case '[': st.push(n); break; case ')': case ']': case '}': if(st.isEmpty() || n != map.get(st.pop())) { return false; } } } return st.isEmpty(); } }||< スタックを使った回答です。 入力をforで回し、 左部分でしたらスタックに押し込み、 右部分でしたらスタックからポップした物と一致するかを判断します。 最後にスタックが空だったらすべての括弧が有効に閉じられています。 Time O(n)です。 今日は以上。