這是較容易的編碼任務(wù)之一，但是您仍然可以在一些初步的技術(shù)篩選中達(dá)到要求。 問題看起來像這樣：

給定僅包含字符'(' ， ')' ， '{' ， '}' ， '['和']'的字符串，請確定輸入字符串是否有效。

括號必須以正確的順序閉合， "()"和"()[]{}"均有效，而"(]"和"([)]"則無效。

描述取自Leetcode（c） 。

您如何解決？

我們一直在使用這項任務(wù)進(jìn)行技術(shù)篩選。 有趣的是，有多少人真的不知道該如何處理（請注意，這是Leetcode上的“輕松”類別）。 有些人嘗試使用正則表達(dá)式。 有些人試圖想出一種蠻力解決方案，遍歷字符串并計算開括號和閉括號。 但是，如果您考慮一下，您將理解，兩者都不足以。 例如，如何在（[）]最簡單的情況下計數(shù)幫助？

您應(yīng)該想到的解決方案是stack ，但是如果您從未接受過解決編碼問題的培訓(xùn)，則可能不會。 為什么要堆疊？ 好吧，因為僅當(dāng)您看到閉合的括號時，才可以檢查這對括號或括號的完整性； 但這意味著打開的那個應(yīng)該放在某個地方等待，并在某些數(shù)據(jù)結(jié)構(gòu)之上進(jìn)行檢查。 允許LIFO訪問的結(jié)構(gòu)是一個堆棧 。 碰巧我們在Java中有一個現(xiàn)成的Stack類 。

那么，簡單的解決方案如何？
基本思想是，您開始遍歷字符串。 如果符號是打開符號之一，則將其推入堆棧。 如果即將關(guān)閉，您可以查看堆棧，看看是否匹配。 如果是，則將其從堆棧中彈出。 如果堆棧最后為空，則返回true。

import java.util.*;public class Groups{private static final List<Character> OPEN = Arrays.asList('(', '{', '[');private static final List<Character> CLOSE = Arrays.asList(')', '}', ']');public static boolean groupCheck(String s){if (s == null || s.length() == 0) {return true;}Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char current = s.charAt(i);if (isOpen(current)) {stack.push(current);} else {if (stack.isEmpty()) {return false;}char prev = stack.peek();if (isMatch(prev, current)) {stack.pop();}}}return stack.isEmpty();}private static boolean isOpen(char c) {return OPEN.contains(c);}private static boolean isClose(char c) {return CLOSE.contains(c);}private static boolean isMatch(char prev, char next) {return isOpen(prev) && (OPEN.indexOf(prev) == CLOSE.indexOf(next));}}

還有其他解決方法嗎？ 如果您不敢想到該怎么辦？ 與往常一樣，有多種方法可以解決問題。 讓我們看這個例子： （[]）{} 。

讓我們嘗試替換正確匹配的對：

“（[]] {}”。replace（“ []”，“”）=>“（）{}”。replace（“（（）”，“”）=>“ {}”。replace（“ {} ”，“”）=>“”

因此，我們可以循環(huán)遍歷字符串，用空字符串替換“ {}”，“（）”和“ []”。 當(dāng)結(jié)果為空時，表示所有對都匹配。 如果沒有變空怎么辦？ 我們?nèi)绾螖[脫周期？ 好吧，我們需要檢查一輪替換后字符串的長度是否已更改。 如果還沒有，那么我們就破產(chǎn)了。

public class Groups{public static boolean groupCheck(String s) {int len;do {len = s.length();s = s.replace("()", "");s = s.replace("{}", "");s = s.replace("[]", "");} while (len != s.length());return s.length() == 0;} }

看起來更好。 簡單易讀，但實際上是否更好？ 我會說不，不是。 為什么？ 好吧，因為String類是不可變的 ，因此每次執(zhí)行s.replace（）時，我們都會在堆上創(chuàng)建一個新的字符串對象。

那么，如何最好地做到這一點(diǎn)呢？ 我們可以使用StringBuilder類重寫代碼嗎？ 好吧，不是直接的，因為它沒有replaceAll方法。 您必須使用現(xiàn)有的replace方法自己編寫。 Apache Commons庫中有一個StrBuilder類，它確實具有此方法，但它不是標(biāo)準(zhǔn)的Java類，您必須添加一個依賴項。

因此，即使這個簡單的任務(wù)也可以給您一些思考。 但是，對于面試，任何解決方案都可以。 如果堆棧不是您腦海中最先想到的，那么您可以不做任何事情。

翻譯自: https://www.javacodegeeks.com/2017/02/interview-questions-verify-braces.html

總結(jié)

以上是生活随笔為你收集整理的面试问题：检查牙套的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。