題目

https://leetcode.com/problems/valid-parenthesis-string/

題解

帶緩存的暴力遞歸，非常挫。用一個 string 模擬 stack，方便緩存記錄狀態(tài)。

class Solution {public boolean checkValidString(String s) {StringBuilder stack = new StringBuilder();Map<String, Boolean> map = new HashMap<>();return process(stack, s, 0, map);}public boolean process(StringBuilder sb, String s, int i, Map<String, Boolean> map) {String key = sb.toString() + ":" + i;if (map.containsKey(key)) return map.get(key);if (i == s.length()) {map.put(key, sb.length() == 0);return sb.length() == 0;}if (s.charAt(i) == '(') {sb.append('(');boolean result = process(sb, s, i + 1, map);map.put(key, result);return result;} else if (s.charAt(i) == ')') {if (sb.length() == 0 || sb.charAt(sb.length() - 1) != '(') {map.put(key, false);return false;} else {sb.deleteCharAt(sb.length() - 1);boolean result = process(sb, s, i + 1, map);map.put(key, result);return result;}} else {// condition 1: * = ''StringBuilder p1 = new StringBuilder(sb);if (process(p1, s, i + 1, map)) {map.put(key, true);return true;}// condition 2: * = '('StringBuilder p2 = new StringBuilder(sb);p2.append('(');if (process(p2, s, i + 1, map)) {map.put(key, true);return true;}// condition 3: * = ')'if (sb.length() != 0 && sb.charAt(sb.length() - 1) == '(') {StringBuilder p3 = new StringBuilder(sb);p3.deleteCharAt(p3.length() - 1);if (process(p3, s, i + 1, map)) {map.put(key, true);return true;}}}map.put(key, false);return false;} }

評論區(qū)解答

很優(yōu)雅：Java, Very easy solution. No recursion or dp.

Think this might be logically easiest solution for this problem.
Check from left to right and then check from right to left.
When check from left to right, take all ''s as ‘(’, to see whether can match all ')'s.
And, When check from right to left, take all ''s as ‘)’, to see whether can match all '('s.
If both checks are valid, then the string is valid.

p.s. Thanks to @vagnihotri1117, we can return true if the first check returns bal=0.

public boolean checkValidString(String s) {int bal = 0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(' || s.charAt(i) == '*') bal++;else if (bal-- == 0) return false;}if (bal == 0) return true;bal = 0;for (int i = s.length()-1; i >= 0; i--) {if (s.charAt(i) == ')' || s.charAt(i) == '*') bal++;else if (bal-- == 0) return false;}return true; } 超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的leetcode 678. Valid Parenthesis String | 678. 有效的括号字符串（带缓存的暴力递归）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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