20_有效的括号

20_有效的括号

package 棧;

import java.util.HashMap;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/valid-parentheses/
 * 
 * @author Huangyujun
 *
 */
public class _20_有效的括号 {
//     public boolean isValid(String s) {
//         //一般做法：成對替換成空字元串
//         while(s.contains("{}") || s.contains("[]") || s.contains("()")) {
//             s = s.replace("{}", "");
//             s = s.replace("()", "");
//             s = s.replace("[]", "");
//         }
//         return s.isEmpty();
//     }

    //補充java： 字元串也是由一個個字元組成的
//    String str = ...;
//    for(int i = 0; i < str.lenth(); i++) {
//        char c = str.charAt(i);
//    }
    
    //補充java：
    //字元串數組長度 （是其内部屬性）：length
    //字元串長度 （是其内部的方法）：length()
    
//    private HashMap<Character,Character> map = new HashMap<>();
//    public _20_有效的括号() {    //細節：需要注意構造方法名的統一（跟力扣上的方法名進行統一，也可以通過搞成static變量，在static塊中進行添加“詞彙量”）
//        //添加字典“詞彙量”
//        map.put('(', ')');
//        map.put('[', ']');
//        map.put('{', '}');
//    }
    private static HashMap<Character,Character> map = new HashMap<>();
    static {
        //添加字典“詞彙量”
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
    }
    
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        int len = s.length();
        for(int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }else {
                //判斷特殊情況，棧中無 左括号
                if(stack.isEmpty())    return false;
                char left = stack.pop();
                
//                ①if(left == '(' && c != ')')    return false;
//                ②if(left == '[' && c != ']')    return false;
//                ③if(left == '{' && c != '}')    return false;
                //①②③通過map（字典）進行優化
                if(c != map.get(left))    return false;
                
            }
        }
        return stack.isEmpty();
    }
}