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));
}
```