【Code筆記本】Valid Parentheses

Given a string 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.

Note that an empty string is also considered valid.

解決這個問題的方法其實是顯而易見的，一定是建一個stack，把所有的element做判斷後push進去或是把對應元素pop出來。我剛看到這個題想的問題有兩個，一個是怎麼簡潔有效地判斷bracket的對應關係，if else 固然可以，但是如果對應元素多了就比較不簡潔了，所以我建立了兩個有對應關係的library，以增加其普適性。第二個問題是判斷左右bracket數量的平衡性，所以裡面用了兩次check 是否是empty，第一次check是防止right太多，第二次防止push/pop之後還有left bracket存在。

我的解法如下：

class Solution {

public:

bool isValid(string s) {

stack bracket;

char left[3] = {"(", "[", "{"};

char right[3] = {")", "]", "}"};

for (int i = 0; i

if (s[i] == left[0] || s[i] == left[1] || s[i] == left[2])

bracket.push(s[i]);

// If the element is left bracket

else

//...right

{

if (bracket.empty())

return false;

//if there is nothing in the stack when a right bracket comes

bool find = false;

int j = 0;

while(j

if (s[i] == right[j] && bracket.top() == left[j]){

bracket.pop();

find = true;

}

j++;

}

if(!find)

return false;

}

}

return bracket.empty();

}

};

大神解法：

很明顯，用boolean去判斷對應關係是更加成熟和簡潔的方式。路漫漫其修遠兮，見賢思齊啦！

btw，青旅lobby有黑人在彈吉他唱歌誒，聲音很輕但還是很厲害。

王釗，Matthew

2018.8.5 in Prague

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！