括号匹配-算法详细题解LeetCode

题目:有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"

输出: true

示例 2:

输入: "()[]{}"

输出: true

示例 3:

输入: "(]"

输出: false

/**

 * @author cosefy

 * @date 2020/6/8

 */

public class ValidParenthesis {

    public static void main(String[] args) {

        String s = "";

        System.out.println(s);

        boolean b = isValid_Test1(s);

        boolean b = isValid_Test2(s);

        System.out.println("结果是： " + b);

    }

    //解法一：采用栈的辅助

    /*

    思路：循环遍历字符串，遇到左括号就压栈，否则就出栈，出栈时判断栈是否为空，遍历结束后，记得判断栈空。

    分析：一趟遍历，时间复杂度为O（n）

    易错点：注意栈空的判断

    思考：

        -执行用时很少，但内存消耗有点多，考虑是否有办法节约内存。

        -可以判断字符串的长度是否为0或者为奇数，直接返回结果

     */

    public static boolean isValid_Test1(String s) {

        if (s.length() == 0)

            return true;

        if (s.length() % 2 != 0)

            return false;

        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {

            if (c == '(' || c == '{' || c == '[') {

                stack.push(c);

            } else {

                if (stack.isEmpty())

                    return false;

                char cc = stack.pop();

                if ((cc == '(' && c != ')') || (cc == '{' && c != '}') || (cc == '[' && c != ']'))

                    //上述判断语句也可用HashMap存储三对括号来查询实现。

                    return false;

            }

        }

        return stack.isEmpty();

    }

    //解法二：数组辅助实现

    /*

    思路：开辟一个数组存放字符，利用一个变量来访问数组，若遍历到左括号，变量自加1，否则变量自减1，

    分析：此方法相对来说用时更少。

     */

    public static boolean isValid_Test2(String s) {

        if (s.length() == 0)

            return true;

        if (s.length() % 2 != 0)

            return false;

        char[] chars = new char[s.length()];

        int index = -1;

        for (char c : s.toCharArray()) {

            if (c == '(' || c == '{' || c == '[') {

                index++;

                chars[index]=c;

            }else {

                if(index==-1)

                    return false;

                if(c==')'&&chars[index]=='('||

                        c=='}'&&chars[index]=='{'||

                        c==']'&&chars[index]=='[')

                    index--;

            }

        }

        return index==-1;

    }

}

巴特西

括号匹配-算法详细题解LeetCode

题目:有效的括号

最新文章

热门文章