dp括號(hào)匹配 網(wǎng)易面試題

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

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

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

描述取自Leetcode（c） 。

您如何解決？

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

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

那么，簡(jiǎn)單的解決方案如何？
基本思想是，您開始遍歷字符串。 如果符號(hào)是打開符號(hào)之一，則將其推入堆棧。 如果即將關(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));}}

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

讓我們嘗試替換正確匹配的對(duì)：

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

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

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

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

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

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

dp括號(hào)匹配 網(wǎng)易面試題

總結(jié)

以上是生活随笔為你收集整理的dp括号匹配 网易面试题_面试题：大括号验证的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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