MayChallenge (61) | Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
  1. Insert a character
  2. Delete a character
  3. Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
In book of Le Minh Hoang, the problem is type Dynamid Programing.

Build the matrix word2.length() row and word1.length() colum. While word2[i] == word1[j], the result equal result before sub problem, is dq[i-1][j-1]. Else, we have 3 options for change. 

1. Insert word2[i] to word1. => dp[i][j] = dp[i][j-1].
2. Delete word1[j] => dp[i][j] = dp[i-1][j].
3. Replace word1[j] to word2[i] => dp[i][j] = dp[i-1][j-1].

My code:
Humm, i completed challenge May. Thank you for reading !

Nhận xét

  1. hmm ... i want to say i miss you 🙆🏼‍♀️

    Trả lờiXóa
    Trả lời
    1. I want to say i'm thank you. If you want contact me, my fb of me is: fb.com/iamthankyou

      Xóa
    2. I make friends with you on Facebook and always follow you. But maybe you haven't realized me.

      Xóa
    3. You still haven't recognized me? Why?

      Xóa
  2. Nhận xét này đã bị tác giả xóa.

    Trả lờiXóa

Đăng nhận xét

Bài đăng phổ biến từ blog này

Hiểu về Norm Regularization

Những thuật toán nền tảng trong lĩnh vực Trí tuệ nhân tạo (Artificial Intelligence I)