当先锋百科网

首页 1 2 3 4 5 6 7

Leetcode 20题

Leetcode 20题

题目描述：

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]'的字符串 s ，判断字符串是否有效。有效字符串需满足：
1）左括号必须用相同类型的右括号闭合。
2）左括号必须以正确的顺序闭合。

解题思路：

1）将字符串中的‘()’替换为‘’，‘[]’替换为‘’,’{}'替换为；‘’, 替换完之后字符串的长度若为0，则返回true，若不等于0，则返回false

class Solution {
    public boolean isValid(String s) {
        int length = s.length()/2;
        for (int i = 0; i < length; i++) {
            s = s.replace("()","").replace("[]","").replace("{}","");
        }
        return s.length() == 0;
    }
}

2）利用栈遍历字符串的字符。在遍历的过程中，若栈为空或者没有我们要匹配的字符，则返回false

class Solution01{
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || c!=stack.pop()) return false;
        }
        return stack.isEmpty();
    }
}

验证过程：

package no20;

import java.util.Stack;

//给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。
//        有效字符串需满足：
//        左括号必须用相同类型的右括号闭合。
//        左括号必须以正确的顺序闭合。

class Solution {
    public boolean isValid(String s) {
        int length = s.length()/2;
        for (int i = 0; i < length; i++) {
            s = s.replace("()","").replace("[]","").replace("{}","");
        }
        return s.length() == 0;
    }
}

class Solution01{
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || c!=stack.pop()) return false;
        }
        return stack.isEmpty();
    }
}

public class No20 {
    public static void main(String[] args) {
        Solution01 solution = new Solution01();
        boolean a = solution.isValid(new String("()[]{}"));
        System.out.println(a);
    }
}