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:
- Insert a character
- Delete a character
- 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 !
hmm ... i want to say i miss you 🙆🏼♀️
Trả lờiXóaI want to say i'm thank you. If you want contact me, my fb of me is: fb.com/iamthankyou
XóaI make friends with you on Facebook and always follow you. But maybe you haven't realized me.
Xóahmm
XóaYou still haven't recognized me? Why?
XóaNhận xét này đã bị tác giả xóa.
Trả lờiXóa