Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Leetcode20 – Valid parentheses

above

This article is the rookie brush problem record, only used as notes, not the best solution.

The title information

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

An open parenthesis must be closed with a close parenthesis of the same type. The left parentheses must be closed in the correct order.

Analysis of the problem

Method 1

This solution is mainly operated by stack. The string is first iterated over, and if an open parenthesis is encountered, it is placed on the stack. If a close parenthesis is encountered, the top element is first extracted from the stack. If the top element of the stack is an open parenthesis matching the close parenthesis, the loop continues forward. If the top of the stack element does not match the close parenthesis, then the top of the stack element and the close parenthesis are not parentheses, and the string is an invalid string. When the entire string traversal is complete and all parentheses match if the stack element is empty, the string is considered a valid string. The code is as follows:

public boolean isValid(String s) {
    Stack stack = new Stack();
    for (int i = 0; i < s.length(); i++) {
        switch (s.charAt(i)){
            case '(':
            case '[':
            case '{':
                stack.add(s.charAt(i));
                break;
            case ']':
                if('[' == (char)stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
                break;
            case '}':
                if('{' == (char)stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
                break;
            case ')':
                if('(' == (char)stack.peek()){
                    stack.pop();
                }else{
                    return false;
                }
                break;
            default:
                return false;
        }
    }
    if(stack.empty()){
        return true;
    }else{
        return false;
    }
}
Copy the code

Method 2

This solution is mainly achieved through string substitution. Replaces all matching strings with null, or a valid string if the final result is an empty string. Otherwise, the string is considered invalid. The code is as follows:

public boolean isValid(String s) {
    while (s.indexOf("[]") > -1 || s.indexOf("()") > -1 || s.indexOf("{}") > -1){
        s = s.replace("[]","");
        s = s.replace("{}","");
        s = s.replace("()","");
    }
    if("".equals(s)){
        return true;
    }
    return false;
}
Copy the code

Complexity analysis

  • Time complexity O (n)
  • Space complexity O (n)

Afterword.

  • How many events through the ages? Leisurely. The Yangtze River is still rolling.