Image From LeetCodeImage From LeetCode

今天我們要講解的是 [Valid Parentheses]，這在 LeetCode 算是比較簡單的題目，讓我們一起開始吧！

進來之前請先注意，我的方式不一定完全正確，只是依照我自己的理念進行撰寫，所以如果程式上有什麼更好的解法，歡迎提出見解。

這次題目

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
2
Input: s = "()"
Output: true
1
2
Input: s = "()[]{}"
Output: true
1
2
Input: s = "(]"
Output: false

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of parentheses only ‘()[]{}’.

自已解法

這組題目主要是驗證是否為閉鎖的括號，透過帶進來的值去驗證裡面的括號是否符合我們所要的規範，首先我們新增一個盒子，裡面放置需要進行驗證的字元，並且加入迴圈來進行驗證各個字元。

1
2
3
4
5
6
7
8
9
10
11
/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s) {
    let stack = [];

    for (let char of s) {

    }
 }

接續我們先確認當下的字元是否為開口，也就是(,{,[等，如果是的話加入到驗證的盒子，如果不是的話就代表此次開口已經結束，接下來要驗證的是上一個欄位是否為他的閉鎖，是的話可以透過pop來進行消除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s) {
    let stack = [];

    for (let char of s) {
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            if (
                (char === ')' && stack[stack.length - 1] !== '(') ||
                (char === '}' && stack[stack.length - 1] !== '{') ||
                (char === ']' && stack[stack.length - 1] !== '[')
            ) {
                return false;
            }
            stack.pop();
        }
    }
 }

接續上一個，除了驗證是否閉鎖外，還要確認盒子是否都清空了，最後結果我們再次確認stack是否有完全清空，如果是的話就代表此次驗證成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string} s
 * @return {boolean}
 */
 var isValid = function(s) {
    let stack = [];

    for (let char of s) {
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else {
            if (!stack.length ||
                (char === ')' && stack[stack.length - 1] !== '(') ||
                (char === '}' && stack[stack.length - 1] !== '{') ||
                (char === ']' && stack[stack.length - 1] !== '[')
            ) {
                return false;
            }
            stack.pop();
        }
    }

    return !stack.length;
 }

實作結果

這次的寫法雖然簡單，但當時第一次做整個繞了一大圈，我還針對不同符號加入正數跟負數的做法並且加入回文驗證，想當然而變得極度複雜導致效能太差，後來理解別人的做法才知道原來那麼簡單，透過push和pop的方式即可完美解決驗證。

Image From LeetCodeImage From LeetCode