Programming

Leetcode-20. Valid Parentheses

By PattySung 07 July 2023
Leetcode-20. Valid Parentheses

Given a string s containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Example 4: 自己做的測試

Input: s ="([{])}"
Output: false

->所以一定要剛好一個相同的符號正反一對，不然會return false

<解題>

  1. 一定要剛好一個相同的符號正反一對，不然會return false
  2. 先把正的符號先push進去stack
  3. 如果有一樣的反符號配對，且剛好在最上面的話，就pop出來；不然就false
  4. 最後如果都有成對，stack就是空的，所以stack.isEmpty()=true返回

class Solution {
    public boolean isValid(String s) {

        if(s.length()%2!=0) return false;

        Stack<Character> stack = new Stack<>();
        //Deque<String> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '('|| c =='{' || c=='['){
                stack.push(c);
            } else if (c =='}' && !stack.isEmpty() && stack.peek()=='{'){
                stack.pop();
            } else if (c ==']' && !stack.isEmpty() && stack.peek()=='['){
                stack.pop();
            } else if (c ==')' && !stack.isEmpty() && stack.peek()=='('){
                stack.pop();
            } else{
                return false;
            }
        }
        return stack.isEmpty();
    }
}


class Solution {
    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.empty(){
                    return false;
                }
                char temp=stack.pop();
                if(c!=temp){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
    //[{()}]
    //

}

補充

STACK.peek() -> 返回值：該方法返回堆棧頂部的元素，如果堆棧為空，則返回NULL。

舉例：


public class StackDemo { 
    public static void main(String args[]) 
    { 
        // Creating an empty Stack 
        Stack<String> STACK = new Stack<String>(); 
  
        // Use push() to add elements into the Stack 
        STACK.push("Welcome"); 
        STACK.push("To"); 
        STACK.push("Taiwan");  
  
        // Displaying the Stack 
        System.out.println("Initial Stack: " + STACK); 
  
        // Fetching the element at the head of the Stack 
        System.out.println("The element at the top of the"
                           + " stack is: " + STACK.peek()); 
  
        // Displaying the Stack after the Operation 
        System.out.println("Final Stack: " + STACK); 
    } 
}

輸出：


Initial Stack: [Welcome, To, Taiwan]
The element at the top of the stack is: Taiwan
Final Stack: [Welcome, To, Taiwan]