一维DP

划分型：f[] means XXXX ending with i

word break

longest valid parentheses

decode ways

Longest Valid Parentheses

• 不能算Hard, 但是转移方程需要考虑坐标edge case, bug free不容易

• 划分型类似Longest Palindromic Substring，word break思路

public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        int[] f = new int[n];
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') { //“（）”
                    f[i] = 2 + (i >= 2 ? f[i - 2] : 0);
                } else if (i - f[i-1] - 1 >= 0 && s.charAt(i - f[i-1] - 1) == '(') {
                    f[i] = 2 + f[i-1] + (i - f[i-1] - 2 >= 0 ? f[i - f[i-1] - 2] : 0);
                }
            }
            max = Math.max(max, f[i]);
        }
        return max;
    }

Decode Ways

• 注意corner case, any valid substring must starts with non-zero

• how to handle "0000" ?

• state:f[i] means num of decode ways for s.substring(i)

• function:

  • f[i] = isValid(s.substring(i, i + 1)) && f[i + 1] + isValid(s.substring(i, i + 2)) && f[i + 2]

• oneDigit != 0

• 10 <= twoDigits <= 26

• res: f[0]

• initialize:

  • f[n] = 0

  • f[n - 1] = isValid(s.substring(n - 1)) ? 1 : 0

  • f[n - 2] = isValid(s.substring(n - 2)) ? 1 + f[n - 1] : 0

• 面试还是写从dfs -> memo的思路更make sense一点

• 除非面试官要求optimal space complexity-> DP with rolling array

class Solution {
    /*    
    brute force: DFS
    decode("226") = decode("26") + isValid("22") && decode("6")
    
    state:f[i] means num of decode ways for s.substring(i)
    function: 
    f[i] = isValid(s.substring(i, i + 1)) && f[i + 1] + isValid(s.substring(i, i + 2)) && f[i + 2]
    oneDigit != 0
    10 <= twoDigits <= 26
    res: f[0]
    initialize: 
    f[n] = 0
    f[n - 1] = isValid(s.substring(n - 1)) ? 1 : 0
    f[n - 2] = isValid(s.substring(n - 2)) ? 1 + f[n - 1] : 0
    
    O(N) Time and O(N) Space
    can use rolling array to optimize space complexity to O(1)
    
    */
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] f = new int[n + 1];
        //initialize
        f[n] = 1;
        f[n - 1] =  s.charAt(n - 1) != '0' ? 1 : 0;
        for (int i = n - 2; i >= 0; i--) {
            char c = s.charAt(i);
            //one digit, need to make sure it's not '0'
            if (c != '0') {
                f[i] += f[i + 1];
            }
            int twoDigits = (s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0';
            if (twoDigits >= 10 && twoDigits <= 26) {
                f[i] += f[i + 2];
            }
        }
        return f[0];
    }
}