Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

583. Delete Operation for Two Strings

Time: $O(mn)$

Space: $O(mn)$

			


class Solution {
 public:
  int minDistance(string word1, string word2) {
    const int k = lcs(word1, word2);
    return (word1.length() - k) + (word2.length() - k);
  }

 private:
  int lcs(const string& A, const string& B) {
    const int m = A.length();
    const int n = B.length();
    // dp[i][j] := LCS's length of A[0..i) and B[0..j)
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (A[i - 1] == B[j - 1])
          dp[i][j] = 1 + dp[i - 1][j - 1];
        else
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    return dp[m][n];
  }
};




			


class Solution {
  public int minDistance(String word1, String word2) {
    final int k = lcs(word1, word2);
    return (word1.length() - k) + (word2.length() - k);
  }

  private int lcs(final String A, final String B) {
    final int m = A.length();
    final int n = B.length();
    // dp[i][j] := LCS's length of A[0..i) and B[0..j)
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (A.charAt(i - 1) == B.charAt(j - 1))
          dp[i][j] = 1 + dp[i - 1][j - 1];
        else
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

    return dp[m][n];
  }
}




			


class Solution:
  def minDistance(self, word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)
    dp = [0] * (n + 1)

    for j in range(n + 1):
      dp[j] = j

    for i in range(1, m + 1):
      newDp = [i] + [0] * n
      for j in range(1, n + 1):
        if word1[i - 1] == word2[j - 1]:
          newDp[j] = dp[j - 1]
        else:
          newDp[j] = min(newDp[j - 1], dp[j]) + 1
      dp = newDp

    return dp[n]