一道阿里面试算法题

面试过程中出的一道算法题，应该算easy程度吧，面试过程中理解错了，审题很重要！ 题目：给定一串括号，判断是否符合规则，即相应左右括号数量匹配，右括号出现在左括号右面。

示例：

输入：([)[]{()}
输出：false

输入：){[(]})
输出：false

输入：{[(]})
输出：true

思路

用map记录每种右括号的数量，遍历字符串，遇到左括号，将相应右括号数量+1；遇到右括号，如果此时value值为0或map还未放入元素，则返回false，否则相应value值-1。最后返回三个value值是否都为0。

代码

/***
 * 给定一个字符串，判断是否有效
 *（各种括号数量匹配即有效）
 * 输入：([)[]{()} 输出：false
 *      ){[(]}) 输出：true
 */
import java.util.*;
public class MainAlibaba {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(helper(s));
    }
    public static boolean helper(String s){
        char[] ch = s.toCharArray();
        //遇到左括号相应map的size + 1,遇到右括号-1
        Map<Character, Integer> map = new HashMap<>();
        for(char c : ch){
            if(c == '('){
                map.put(')', map.getOrDefault(')', 0) + 1);
            }
            else if(c == '[')
                map.put(']', map.getOrDefault(']', 0) + 1);
            else if(c == '{')
                map.put('}', map.getOrDefault('}', 0) + 1);
            else if(c == ')'){
                if(map.isEmpty() || map.get(')') == 0)
                    return false;
                else map.put(')', map.get(')') - 1);
            }
            else if(c == ']'){
                if(map.isEmpty() || map.get(']') == 0)
                    return false;
                else map.put(']', map.get(']') - 1);
            }
            else if(c == '}'){
                if(map.isEmpty() || map.get('}') == 0)
                    return false;
                else map.put('}', map.get('}') - 1);
            }
        }
        return map.get(')') == 0 && map.get(']') == 0 && map.get('}') == 0;
    }
}