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.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
一個(gè)僅由 '(', ')', '{', '}', '[' 和 ']' 組成的字符串券犁，判斷是否符合要求：
- 判斷符號(hào)是否成對(duì)促绵；
- 成對(duì)的符號(hào)要在對(duì)立的位置宁玫。
空字符串也是符合要求的。
解：
思路一惋耙，成對(duì)符號(hào)前面為a，后面為b。用一個(gè)map去記錄成對(duì)的符號(hào) b->a 的映射台妆，用一個(gè) stack 去記錄 a，利用 stack 先進(jìn)后出的特性去完成匹配胖翰。從頭開始遍歷接剩，判斷當(dāng)前符號(hào)是否存在map中，存在萨咳，表明是b懊缺，那么取出map中對(duì)應(yīng)的a去與stack中最后加入的符號(hào)進(jìn)行匹配，匹配不上培他，完了鹃两，這肯定不是合法的，直接return false舀凛；能匹配上俊扳，stack.pop()。如果是a腾降，加入到stack中拣度。到最后，如果stack是空的螃壤，說明是合法的抗果。由于只進(jìn)行一輪遍歷，時(shí)間復(fù)雜度為O(n)奸晴，空間復(fù)雜度冤馏，最壞的情況下，比如全為左符號(hào)寄啼，需要O(n)逮光。
思路二，有一個(gè)特別巧的思路墩划，寫個(gè)死循環(huán)涕刚，一直把成對(duì)的符號(hào)替換成空，直到替換之后乙帮，長度沒有變杜漠。最后字符串不為空，則表示不合法。
以下為代碼：
public boolean isValid(String s) {
int length;
do {
length = s.length();
s = s.replace("()", "").replace("{}", "").replace("[]", "");
} while (length != s.length());
return s.isEmpty();
}
雖然思路二思路驾茴、代碼都很簡(jiǎn)單盼樟，但是時(shí)間復(fù)雜復(fù)雜度很高，replace使用正則去匹配锈至，然后再去替換晨缴，內(nèi)部還有一層循環(huán)，最壞情況下需要循環(huán)n/2次峡捡，但是一次要匹配3次击碗。時(shí)間復(fù)雜度約為O(n2)。
