linye's Blog

全端工程師心得分享

0%

[LeetCode]20. Valid Parentheses

發表於 分類於 ，

Algorithm I 筆記撰寫計畫 第九天第一題，共兩題。

點我開啟限制與範例

限制:

  • 1 <= s.length <= 104
  • s consists of parentheses only '()[]{}'.

Example 1:

1
2
Input: s = "()"
Output: true

Example 2:

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

Example 3:

1
2
Input: s = "(]"
Output: false

筆記

這題要訓練 stack 的運用，解題步驟如下：

  1. 建立一個 stack ，運用他 LIFO 的特性，我們可以很好的對剛插入的值進行比較。
  2. 遍歷 s
  3. 遇到左括弧( '(', '[', '{' )，都塞進去 stack
  4. 遇到右括弧( ')', ']', '}' )，就檢查 stack 最後一個值，
    • 如果一樣，就把這個值刪掉( pop() )
    • 如果不一樣，代表這個字串不合法，回傳 false
  5. 最後檢查 stack 裡還有沒有值，有就傳 false ，沒有就傳 true

Java iterative solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
  public boolean isValid(String s) {
    // Create stack for search.
    Stack<Character> stack = new Stack<Character>();

    // Push first element to avoid exception.
    stack.push(s.charAt(0));

    // travel tho s.
    for (int i = 1; i < s.length(); i++) {

      // if taking [')', '}', ']'], than we check what if stack top is the other part, if is, we pop the other part.
      if ((s.charAt(i) == '}' && !stack.isEmpty() && stack.peek() == '{') ||
        (s.charAt(i) == ']' && !stack.isEmpty() && stack.peek() == '[') ||
        (s.charAt(i) == ')' && !stack.isEmpty() && stack.peek() == '(')
      ) stack.pop(); 

      // if taking ['(', '{', '['], we put this element into stack.
      else if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'

      // if not matching by top two rule, we return false.
      ) stack.push(s.charAt(i));
      else return false;
    }
    
    // if stack stil contain element that mean this test case is invalid, we return false.
    if (!stack.empty()) return false;

    return true;
  }
}

成績

<!-- Language Runtime Beats Memory Usage Beats
Java 1 ms 80.63% 43.9 MB 73.27%
TypeScript 77 ms 95.35% 45.4 MB 22.74% -->

score-image