Tìm số phép biến đổi tối thiểu để 2 string giống nhau

Nguồn: http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
Bài viết này chỉ là dịch thô từ nguồn trên do khả năng của mình có hạn nên rất mong nhận được sự góp ý từ các bạn

Cho 2 string str1 và str2 và các phép biến đổi cơ bản để thay đổi string str1. Tìm số biến đổi tối thiểu cần để str1 giống str2.

1. Thêm
2. Xóa
3. Thay thế

Tất cả các phép trên là tương đương.




Ví dụ:

Input:   str1 = "geek", str2 ="gesek"
Output:  1
We can convert str1 into str2 by inserting a 's'.

Input:   str1 = "cat", str2 = "cut"
Output:  1
We can convert str1 into str2 by replacing 'a' with 'u'.

Input:   str1 = "sunday", str2 = "saturday"
Output:  3
Last three and first characters are same.  We basically
need to convert "un" to "atur".  This can be done using
below three operations. 
Replace 'n' with 'r', insert t, insert a

Sau đây là cách giải quyết vấn đề bằng quy hoạch động (Java)

Ta sẽ tạo một bảng dp[m+1][n+1] và dp[i][j] sẽ lưu số phép biến đổi tối thiểu để s1[0..i] giốngs2[0..j]

1. Nếu s1 trống thì phép biến đổi chắc chắn sẽ là j lần thêm và nếu s2 trống thì số phép biến đổi sẽ là j lần xóa chữ cái trong s1

2. Nếu 2 chữ cái đang xét s1[i] và s2[j] của 2 chuỗi giống nhau thì đơn giản ta chẳng phải làm gì và chỉ copy kết quả  dp[i][j] = dp[i-1][j-1]

3. Nếu không giống nhau thì ta có 3 lựa chọn là thêm, xóa và thay thế. Dựa vào các giá trị dp  trước đó ta sẽ biết cái nào hiệu quả hơn  

public class EditDistance {

 public static int min(int x, int y, int z) {
  return Math.min(Math.min(x, y), z);
 }

 public static int editDistDP(String s1, String s2, int m, int n) {
  // create a dp
  int[][] dp = new int[m + 1][n + 1];
  // start
  for (int i = 0; i <= m; i++) {
   for (int j = 0; j <= n; j++) {
    // if s1 empty
    if (i == 0) {
     dp[i][j] = j; // we have to insert
    } else if (j == 0) {
     dp[i][j] = i; // similar
    }
    // if char match
    else if (s1.charAt(i - 1) == s2.charAt(j - 1))
     dp[i][j] = dp[i - 1][j - 1];
    else {
     dp[i][j] = 1 + min(dp[i][j - 1], // insert
       dp[i - 1][j], // remove
       dp[i - 1][j - 1]); // replace
    }
   }
  }

  return dp[m][n];
 }

 public static void main(String[] args) {
  String s1 = "sunday";
  String s2 = "saturdays";
  System.out.println(editDistDP(s1, s2, s1.length(), s2.length()));
 }
}

Output: 3