current position:Home>【LeetCode - Java】20. Valid parentheses (simple)

【LeetCode - Java】20. Valid parentheses (simple)

2022-01-26 22:10:06 Beeemo

1. Title Description

 Insert picture description here

2. Their thinking

The title is relatively simple , classical Their thinking Is the use Stack , From the string Take out the characters in turn and match them with the top of the stack , Unmatched symbols Into the stack , Symbols that can match Out of the stack , Finally, if The stack is empty. Indicates that all parentheses in the string can perfect match .

The problem is coming. , How to judge Whether the two characters are Match relationship Well ? Take a look at ASCII surface , Find out ( And ) Of ASCII Code difference 1,[ And ] and { And } Of ASCII All codes are different 2, So this became my The basis of judgment . Other solutions also use HashMap Realized , But personally, I still think using ASCII More convenient .

stay Java Three solutions have been tried in the implementation , Namely Stack 、 Arrays and linked lists , But the main idea is still stack First in, then out Characteristics of .

3. Code implementation

3.1 Stack (Stack)

	public boolean isValid(String s) {
    
        Stack<Character> chars = new Stack<Character>();
        if (s.length() % 2 == 0) {
    
            for (int i = 0; i < s.length(); i++) {
    
                if (!chars.empty()) {
    
                    if (s.charAt(i) - chars.peek() == 2 || s.charAt(i) - chars.peek() == 1)
                        chars.pop();
                    else
                        chars.push(s.charAt(i));
                } else
                    chars.push(s.charAt(i));
            }
            return chars.empty();
        } else
            return false;
    }

 Insert picture description here

3.2 Array (ArrayList)

public boolean isValid(String s) {
    
        List<Character> characters = new ArrayList<>();
        int l = s.length();
        if (l % 2 == 0) {
    
            for (int i = 0; i < l; i++) {
    
                if (!characters.isEmpty()) {
    
                    if (s.charAt(i) - characters.get(characters.size() - 1) == 1 || s.charAt(i) - characters.get(characters.size() - 1) == 2)
                        characters.remove(characters.size() - 1);
                    else
                        characters.add(s.charAt(i));
                } else
                    characters.add(s.charAt(i));
            }
            return characters.isEmpty();
        } else
            return false;
    }

3.3 Linked list (LinkedList)

public boolean isValid(String s) {
    
        LinkedList<Character> chars = new LinkedList<>();
        if (s.length() % 2 == 0) {
    
            for (int i = 0; i < s.length(); i++) {
    
                if (!chars.isEmpty()) {
    
                    if (s.charAt(i) - chars.getLast() == 2 || s.charAt(i) - chars.getLast() == 1)
                        chars.removeLast();
                    else
                        chars.addLast(s.charAt(i));
                } else
                    chars.addLast(s.charAt(i));
            }
            return chars.isEmpty();
        } else
            return false;
    }

 Insert picture description here

3.4 contrast

obviously , Between the three schemes There is almost no difference between good and bad , Performance is also Almost unanimously , The time complexity is zero O(n),n Is the length of the string . Then I looked at it Official interpretation It's the same thing Ideas , But we haven't found an algorithm with higher efficiency and less space yet .
 Insert picture description here

copyright notice
author[Beeemo],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262210037007.html

Random recommended