DP on String

139. Word Break

public boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (String w : wordDict) {
            if (i - w.length() >= 0 
                && s.substring(i - w.length(), i).equals(w) 
                && dp[i - w.length()]) {
                dp[i] = true;
            }
        }
    }
    return dp[s.length()];
}

91. Decode Ways

Q: the total number of ways to decode it.

dp[i] : the total number of ways to decode at i:

• dp[0] = 1

• dp[1] = 0 when "02" situation, dp[1] = 1 when other situation.

Transition: dp[i] = dp[i - 1] + dp[i - 2];

public int numDecodings(String s) {
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    
    for (int i = 2; i <= s.length(); i++) {
        int one = Integer.valueOf(s.substring(i - 1, i));
        int two = Integer.valueOf(s.substring(i - 2, i));
        if (one >= 1 && one <= 9) {
            dp[i] += dp[i - 1];
        }
        if (two <= 26 && two >= 10) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[s.length()];
}

1143. Longest Common Subsequence

dp[i][j] : longest common subsequence ends at i in text1, j in text2

if s.charAt(i) == t.charAt(j) : dp[i][j] = dp[i - 1][j - 1] + 1

else: dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

583. Delete Operation for Two Strings

The question asks the minimum number of deletion to make word1 and word2 the same, this means to get Longest Common Subsequence of two strings and use the total lens - LCS:

public int minDistance(String word1, String word2) {
    if (word1.equals(word2)) return 0;
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (word1.charAt(i) == word2.charAt(j)) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }
    return word1.length() + word2.length() - 2 * dp[m][n];
}

718. Maximum Length of Repeated Subarray

dp[i][j] : maximum length of common subarray up to i and j

if (A[i] == B[j]) { dp[i][j] = dp[i - 1][j - 1] + 1; }

public int findLength(int[] A, int[] B) {
    if (A == null || B == null || A.length == 0 || B.length == 0) return 0;
    int m = A.length, n = B.length;
    int[][] dp = new int[m + 1][n + 1];
    int max = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } 
            max = Math.max(max, dp[i][j]);
        }
    }
    return max;
}

72. Edit Distance

when s.charAt(i) != t.charAt(j):

• insert = dp[i][j] = dp[i - 1][j] + 1

• delete = dp[i][j] = dp[i][j - 1] + 1

• replace = dp[i][j] = dp[i - 1][j - 1] + 1

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null || word1.equals(word2)) return 0;
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;    
    for (int i = 0; i <= n; i++) dp[0][i] = i;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                int insert = dp[i - 1][j] + 1;
                int delete = dp[i][j - 1] + 1;
                int replace = dp[i - 1][j - 1] + 1;
                dp[i][j] = Math.min(insert, Math.min(delete, replace));
            }
        }
    }
    return dp[m][n];
}

44. Wildcard Matching

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int  i = 1; i <= m; i++) {
        dp[i][0] = false;
    }
    for (int j = 1; j <= n; j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = true;
        } else {
            break;
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) != '*') {
                dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?');
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
    }
    return dp[m][n];
}

10. Regular Expression Matching

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    for (int i = 0; i < p.length(); i++) {
        if (p.charAt(i) == '*' && dp[0][i-1]) {
            dp[0][i+1] = true;
        }
    }
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.') {
                dp[i+1][j+1] = dp[i][j];
            }
            if (p.charAt(j) == '*') {
                if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                    dp[i+1][j+1] = dp[i+1][j-1];
                } else {
                    dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                }
            }
        }
    }
    return dp[m][n];
}

727. Minimum Window Subsequence

[LeetCode] 727. Minimum Window Subsequence 最小窗口序列 - Grandyang - 博客园

dp[i][j] : the starting index of the substring where T has length i and S has length j.

if s.charAt(i) == t.charAt(j), dp[i][j] = dp[i - 1][j - 1]

else: dp[i][j] = dp[i - 1][j]

After find all starting indices, go through then and then length of the window is i - dp[i][n].

    public String minWindow(String S, String T) {
        int m = S.length(), n = T.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        int start = -1, minLen = Integer.MAX_VALUE;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= Math.min(i, n); j++) {
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            if (dp[i][n] != -1) {
                int len = i - dp[i][n];
                if (len < minLen) {
                    minLen = len;
                    start = dp[i][n];
                }
            }
        }
        return start != -1 ? S.substring(start, start + minLen) : "";
    }

Palindrome

516. Longest Palindromic Subsequence

dp[i][j] = dp[i + 1][j - 1] + 2 when s.charAt(i) == s.charAt(j)

dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]) when s.charAt(i) != s.charAt(j)

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (i == j) dp[i][j] = 1;
            else {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }  else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }
    }
    return dp[0][n - 1];
}

1216. Valid Palindrome III

public boolean isValidPalindrome(String s, int k) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (i == j) {
                dp[i][j] = 1;
            } else if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1] + k >= s.length();
}

132. Palindrome Partitioning II

cut[R] is the minimum of cut[L - 1] + 1 (L <= R), if [L, R] is palindrome.

If [L, R] is palindrome, [L + 1, R - 1] is palindrome, and c[L] == c[R].

public int minCut(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n + 1][n + 1];
    int[] min = new int[n];
    for (int r = 0; r < n; r++) {
        min[r] = r;
        for (int l = 0; l <= r; l++) {
            if (s.charAt(l) == s.charAt(r) && (r - l < 2 || dp[l + 1][r - 1])) {
                dp[l][r] = true;
                min[r] = l == 0 ? 0 : Math.min(min[r], min[l - 1] + 1);
            }
        }
    }
    return min[n - 1];
}

Count All Palindromic Subsequence in a given String

Find how many palindromic subsequences (need not necessarily be distinct) can be formed in a given string. Note that the empty string is not considered as a palindrome.

Examples:

Input : str = "abcd"

Output : 4

Explanation :- palindromic subsequence are : "a" ,"b", "c" ,"d"

Input : str = "aab"

Output : 4

Explanation :- palindromic subsequence are :"a", "a", "b", "aa"

Input : str = "aaaa"

Output : 15

Initial Values : i= 0, j= n-1;

CountPS(i,j): Every single character of a string is a palindrome subsequence

if i == j: return 1 // palindrome of length 1

// If first and last characters are same, then we consider it as palindrome subsequence and checkfor the rest subsequence (i+1, j), (i, j-1)

Else if (str[i] == str[j)]: return countPS(i+1, j) + countPS(i, j-1) + 1;

DP

public int countPS(String str) {
    int N = str.length();

    // create a 2D array to store the count
    // of palindromic subsequence
    int[][] cps = new int[N + 1][N + 1];

    // palindromic subsequence of length 1
    for (int i = 0; i < N; i++)
        cps[i][i] = 1;

    // check subsequence of length L is
    // palindrome or not
    for (int L = 2; L <= N; L++) {
        for (int i = 0; i < N; i++) {
            int k = L + i - 1;
            if (k < N) {
                if (str.charAt(i) == str.charAt(k)):
                    cps[i][k] = cps[i][k - 1]
                                + cps[i + 1][k] + 1;
                else:
                    cps[i][k] = cps[i][k - 1]
                                + cps[i + 1][k]
                                - cps[i + 1][k - 1];
            }
        }
    }

    // return total palindromic subsequence
    return cps[0][N - 1];
}

DFS + Memo

static int n;
static int[][] dp = new int[1000][1000];
static String str = "abcb";

// Function return the total
// palindromic subsequence
public int countPS(int i, int j) {

    if (i > j)
        return 0;

    if (dp[i][j] != -1)
        return dp[i][j];
 
    if (i == j)
        return dp[i][j] = 1;

    else if (str.charAt(i) == str.charAt(j))
        return dp[i][j]
            = countPS(i + 1, j) + 
                countPS(i, j - 1) + 1;

    else
        return dp[i][j] = countPS(i + 1, j) + 
                          countPS(i, j - 1) -
                          countPS(i + 1, j - 1);
}