题目

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

题解

带缓存的暴力递归，非常挫。用一个 string 模拟 stack，方便缓存记录状态。

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;
    }
}

评论区解答

很优雅：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;
}