DP on String

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()];
}

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()];
}

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

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

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

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

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

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

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

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

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

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;

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

Last updated

Was this helpful?