[LeetCode] #29 Interleaving String

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    
    // state: dp[i][j] - whether s3.substring(0, i + j) is formed by s1.substring(0, i) and s2.substring(0, j)
    // function: dp[i][j] = (s3[i+j] == s1[i] && dp[i - 1][j]) ||
    //                      (s3[i+j] == s2[j] && dp[i][j - 1])
    // initialize: dp[0][0] = true
    //             dp[i][0] = s3[i] == s1[i] && dp[i - 1][0]
    // result: dp[s1.length()][s2.length()]
    
    public boolean isInterleave(String s1, String s2, String s3) {
        // write your code here
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }
        if (s1.length() + s2.length() < s3.length()) {
            return false;
        }
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;
        for (int i = 1; i <= s1.length() && i <= s3.length(); i++) {
            dp[i][0] = (s1.charAt(i - 1) == s3.charAt(i - 1) && dp[i - 1][0]);
        }
        for (int j = 1; j <= s2.length() && j <= s3.length(); j++) {
            dp[0][j] = (s2.charAt(j - 1) == s3.charAt(j - 1) && dp[0][j - 1]);
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length() && i + j <= s3.length(); j++) {
                dp[i][j] = (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) || (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]);
            }
        }
        
        return dp[s1.length()][s2.length()];
    }
}

[LeetCode] #115 Distinct Subsequences

public class Solution {
    // state: f[i][j] - number of distinct subsequence of T.substring(0, j] in S.substring(0, i]
    // function: f[i][j] = f[i - 1][j] +  (f[i - 1][j - 1], if T[j] == S[i]) // Attn!
    // initialize: f[i][0] = 1
    // result f[T.length()][S.length()]
    public int numDistinct(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) {
            return 0;
        }
        int[][] f = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            f[i][0] = 1;
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                f[i][j] = f[i - 1][j];
                if (t.charAt(j - 1) == s.charAt(i - 1)) {
                    f[i][j] += f[i - 1][j - 1];
                }
            }
        }
        return f[s.length()][t.length()];
    }
}

http://www.cs.cmu.edu/~yandongl/distinctseq.html

[LintCode] #119 Edit Distance

public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    
    // state: f[i][j] - min steps to convert word1.substring(0,i) to word2.substring(0,j) , Attn: when i = 0, j = 0
    // function: f[i][j] = f[i - 1][j - 1], word1[i] == word2[j]
    //                   = Min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1, word1[i] != word2[j]
    // initialze: f[i][0] = i - 1, word1[0] != word2[0]
    //            f[0][i] = i - 1
    // result: f[m][n]
    
    public int minDistance(String word1, String word2) {
        // write your code here
        if (word1 == null || word2 == null || (word1.length() == 0 && word2.length() == 0)) {
            return 0;
        }
        if (word1.length() == 0 || word2.length() == 0) {
            return word1.length() == 0 ? word2.length() : word1.length();
        }
        int[][] f = new int[word1.length() + 1][word2.length() + 1]; // Attn:Why +1?
        for (int i = 0; i <= word1.length(); i++) {
            f[i][0] = i;
        }
        for (int j = 0; j <= word2.length(); j++) {
            f[0][j] = j;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i - 1][j - 1], Math.min(f[i][j - 1], f[i - 1][j])) + 1;
                }
            }
        }
        return f[word1.length()][word2.length()];
    }
}

[LintCode] #79 Longest Common Substring

public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
     
    // state: f[i][j] - length of LCS of A.substring(0, i] and B.substring(0, j]
    // function: f[i][j] = f[i - 1][j - 1] + 1, if A[i] == B[j]
    //                   = 0, if A[i] != B[j]
    // initialize: 
    // result: f[0...A.length - 1][0...B.length - 1]
    
    public int longestCommonSubstring(String A, String B) {
        if (A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }
        int max = 0;
        int[][] f = new int[A.length()][B.length()];
        for (int i = 0; i < A.length(); i++) {
            f[i][0] = A.charAt(i) == B.charAt(0) ? 1 : 0;
            max = Math.max(max, f[i][0]);
        }
        for (int j = 0; j < B.length(); j++) {
            f[0][j] = A.charAt(0) == B.charAt(j) ? 1 : 0;
            max = Math.max(max, f[0][j]);
        }
        for (int i = 1; i < A.length(); i++) {
            for (int j = 1; j < B.length(); j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = 0;
                }
                max = Math.max(max, f[i][j]);
            }
        }
        return max;
    }
}

[LintCode] #77 Longest Common Subsequence

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    
    // state: f[i][j] - longest LCS of A.substring(0, i] and B.substring(0, j]
    // function: f[i][j] = f[i - 1][j - 1] + 1, if A[i] == B[j]
    //                   = Max(f[i - 1][j], f[i][j - 1]), if A[i] != B[j]
    // initialize: f[i][0] = A[i] == B[0] ? 1 : 0,f[0][i] = A[0] == B[i] ? 1 : 0
    // result: f[A.length - 1][B.length - 1]
    
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }
        int[][] f = new int[A.length()][B.length()];
        for (int i = 0; i < A.length(); i++) {
            f[i][0] = A.charAt(i) == B.charAt(0) ? 1 : 0;
        }
        for (int j = 0; j < B.length(); j++) {
            f[0][j] = A.charAt(0) == B.charAt(j) ? 1 : 0;
        }
        for (int i = 1; i < A.length(); i++) {
            for (int j = 1; j < B.length(); j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
        }
        return f[A.length() - 1][B.length() - 1];
    }
}

[LeetCode] #300 Longest Increasing Subsequence

public class Solution {
    // state: f[i] - length of LIS for nums[0...i]
    // function: f[i] = (Max(f[j] + 1), if nums[j] < nums[i]), for all 0 < j < i
    // initialze: f[0] = 1
    // result: Max(f[0...nums.length-1]) //Attn!
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] f = new int[nums.length];
        int maxLength = 1;
        for (int i = 0; i < nums.length; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                    maxLength = Math.max(maxLength, f[i]);
                }
            }
        }
        return maxLength;
    }
}

[LeetCode] #140 Word Break II

Recursion, time complexity: O(2^n),  Time Limit Exceeded

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        helper(s, wordDict, result, new ArrayList<String>(), 0);
        return result;
    }
    
    private void helper(String s, Set<String> wordList, List<String> result, List<String> path, int start) {
        if (start == s.length()) {
            result.add(String.join(" ", path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (wordList.contains(s.substring(start, i))) {
                path.add(s.substring(start, i));
                helper(s, wordList, result, path, i);
                path.remove(path.size() - 1);
            }
        }
    }
}

Recursion + pruning(avoid repeated calculation)

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        boolean[] possible = new boolean[s.length() + 1];
        boolean[] initialized = new boolean[s.length() + 1];
        Arrays.fill(possible, false);
        Arrays.fill(initialized, false);
        helper(s, wordDict, result, new ArrayList<String>(), 0, possible, initialized);
        return result;
    }
    
    private void helper(String s, Set<String> wordList, List<String> result, List<String> path, int start, boolean[] possible, boolean[] initialized) {
        if (start == s.length()) {
            result.add(String.join(" ", path));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            if (wordList.contains(s.substring(start, i)) && (!initialized[i] || possible[i])) {
                int resultN = result.size();
                initialized[i] = true;
                path.add(s.substring(start, i));
                helper(s, wordList, result, path, i, possible, initialized);
                path.remove(path.size() - 1);
                possible[i] = resultN < result.size();
            }
        }
    }
}