尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:300
已运行时间:
目录
  1. 问题思路
    1. ts 实现
    2. 之前的 java 代码实现
      1. 栈实现
      2. HashMap 实现

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:300
已运行时间:

问题思路

将所有的左半边括号 push 到栈内,然后遇到右半边括号,就将其与栈顶元素匹配测试,若能匹配成功则继续匹配,反之输出 false。

在这之间注意比较当栈内没有元素了,而字符串还有待匹配的字符,输出 false,当栈内还有元素,外面与之匹配测试的右半边括号,也输出 false。

ts 实现

function isValid(s: string): boolean {
  let stack: Array<string> = [];
  for (let i of s) {
    if (["(", "[", "{"].includes(i)) {
      stack.push(i);
    } else {
      switch (i) {
        case ")":
          if (stack[stack.length - 1] === "(") {
            stack.pop();
          } else {
            return false;
          }
          break;
        case "]":
          if (stack[stack.length - 1] === "[") {
            stack.pop();
          } else {
            return false;
          }
          break;
        case "}":
          if (stack[stack.length - 1] === "{") {
            stack.pop();
          } else {
            return false;
          }
          break;
      }
    }
  }
  return stack.length ? false : true;
}

之前的 java 代码实现

栈实现

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        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;
            }
        }
        return stack.isEmpty();
    }
}
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i< s.length();i++){
            if (s.charAt(0) == ')' || s.charAt(0) == ']' || s.charAt(0) == '}'){
                return false;
            }
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
                stack.push(s.charAt(i));
            }
            if (s.charAt(i) == ')' || s.charAt(i) == ']' || s.charAt(i) == '}'){
                if (s.charAt(i) == ')'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '(')
                        return false;

                }
                if (s.charAt(i) == ']'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '[')
                        return false;

                }
                if (s.charAt(i) == '}'){
                    if (stack.isEmpty() == true) {
                        return false;
                    }
                    if (stack.pop() != '{')
                        return false;

                }
            }
        }
        if (stack.isEmpty() == true){
            return true;
        } else {
            return false;
        }

    }
}

HashMap 实现

class Solution {
    private static HashMap<Character, Character> map = new HashMap<>();
    static {
        // key - value
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) { // 左括号
                stack.push(c);
            } else { // 右括号
                if (stack.isEmpty()) return false;

                if (c != map.get(stack.pop())) return false;
            }
        }
        return stack.isEmpty();
    }
}

评论区

Beaudar Twikoo

最新评论

Loading...