leetcode - 括号字符串是否有效

括号字符串是否有效

给定一个只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判断字符串是否有效。

有效字符串需满足：  
    左括号必须用相同类型的右括号闭合。  
    左括号必须以正确的顺序闭合。  
    注意空字符串可被认为是有效字符串。  
    
    
```
/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * <p>关键点在于<b>括号对应</b>, 所以需要提前保存括号, 这里使用键值对比较合适</p>
 * @param s
 * @return
 */
public static boolean checkValidString(String s) {
    // 执行用时 :4 ms, 在所有 java 提交中击败了71.86%的用户
    //内存消耗 :34.2 MB, 在所有 java 提交中击败了85.82%的用户
    if(s == null || s .equals("")) {
        return true;
    }
    // 保存括号对应关系
    Map<Character, Character> map = new HashMap<>(3);
    map.put('(',')');
    map.put('{','}');
    map.put('[',']');
    // 左括号集合
    Set<Character> keys = map.keySet();
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char temp = s.charAt(i);
        if(i == 0 && !keys.contains(temp)) {
            return false;
        }
        if(keys.contains(temp)) {
            stack.push(temp);
        } else {
            if(temp != (stack.isEmpty() ? '#' : map.get(stack.pop()))) {
                return false;
            }
        }
    }
    return stack.isEmpty();
    // 没用过java的栈结构, 所以使用了LinkedList, 但是执行时间和空间都比较大
    // 执行用时 :15 ms, 在所有 java 提交中击败了9.23%的用户
    //内存消耗 :36.1 MB, 在所有 java 提交中击败了40.88%的用户
   /* String[] strings = s.split("");
    LinkedList<String> strList = new LinkedList<>();
    for (int i = 0; i < strings.length; i++) {
        if(keys.contains(strings[i])) {
            strList.add(strings[i]);
        } else {
            if(i == 0 || (i != 0 && strList.size() == 0)) {
                return false;
            } else {
                // 判断括号是否匹配
                if(strings[i].equals(map.get(strList.getLast()))) {
                    strList.removeLast();
                    continue;
                } else {
                    return false;
                }
            }
        }
    }
    if(strList.size() == 0) {
        return true;
    }
    return false;*/

}

/**
 * 执行用时 :3 ms, 在所有 java 提交中击败了86.43%的用户
 * 内存消耗 : 34.4 MB, 在所有 java 提交中击败了 84.17%的用户
 * @param s
 * @return
 */
public static boolean checkValidString1(String s) {
    if(s == null || s .equals("")) {
        return true;
    }
    // 保存括号对应关系
    Map<Character, Character> map = new HashMap<>(3);
    map.put(')','(');
    map.put('}','{');
    map.put(']','[');
    // 左括号集合
    Set<Character> keys = map.keySet();
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        Character temp = s.charAt(i);
        if(keys.contains(temp)) {
            Character element = stack.isEmpty() ? '#' : stack.pop();
            if(!element.equals(map.get(temp))) {
                return false;
            }
        } else {
            stack.push(temp);
        }
    }
    return stack.isEmpty();

}

public static void main(String[] args) {
   /* String s1 = "{}[]()";
    String s2 = "([{}])";
    String s3 = "][(){}";
    String s4 = "({(())}";*/
    String s5 = "[])";
    // true
  /*  System.out.println(checkValidString(s1));
    // true
    System.out.println(checkValidString(s2));
    // false
    System.out.println(checkValidString(s3));
    // false
    System.out.println(checkValidString(s4));*/
    System.out.println(checkValidString(s5));
}
```

原文链接:https://www.cnblogs.com/wadmwz/p/11731700.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有