Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character

难度：hard

Solution: Dynamic Programming

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] edit = new int[m + 1][n + 1];
        for(int i = 0; i < m; ++i) {
            edit[i + 1][0] = edit[i][0] + 1;
        }
        for(int j = 0; j < n; ++j) {
            edit[0][j + 1] = edit[0][j] + 1;
        }
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(word1.charAt(i) == word2.charAt(j)) {
                    edit[i + 1][j + 1] = edit[i][j];
                } else {
                    edit[i + 1][j + 1] = Math.min(edit[i][j], Math.min(edit[i + 1][j], edit[i][j + 1])) + 1;
                }
            }
        }
        return edit[m][n];
    }
}

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

难度：hard

Solution: Dynamic Programming

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int s1Len = s1.length(), s2Len = s2.length(), s3Len = s3.length();
        if(s3Len != s1Len + s2Len) {
            return false;
        }
        boolean[][] dp = new boolean[s1Len + 1][s2Len + 1];
        dp[0][0] = true;
        for(int i = 0; i < s1Len; ++i) {
            dp[i + 1][0] = dp[i][0] && s1.charAt(i) == s3.charAt(i);
        }
        for(int j = 0; j < s2Len; ++j) {
            dp[0][j + 1] = dp[0][j] && s2.charAt(j) == s3.charAt(j);
        }
        for(int i = 0; i < s1Len; ++i) {
            for(int j = 0; j < s2Len; ++j) {
                dp[i + 1][j + 1] = (dp[i][j + 1] && s1.charAt(i) == s3.charAt(i + j + 1)) || (dp[i + 1][j] && s2.charAt(j) == s3.charAt(i + j + 1));
            }
        }
        return dp[s1Len][s2Len];
    }
}