Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
583. Deletion of two strings
Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 identical, each step removing one character from either string.
Thought analysis
This problem looks a lot like: 1143. Longest common subsequence (this problem has been covered before), because deleting itself is deleting a character that is not a common subsequence, but if you have done the classic problem of dynamic programming: 72. Edit distance, when calculating the distance between two words, you will feel that the two questions are surprisingly similar, but by contrast, the edit distance question requires multiple insertion and replacement operations when calculating distance.
So this is an obvious problem to solve using dynamic programming.
Dp [I][j] represents the distance between strA(0, I) and strB(0,j). On this basis, we discuss the state transition equation:
If strA [I] = = strB [j], then the dp [I] [j] = = dp [I – 1] [1]
If the strA [I]! = strB[j], then you can choose:
- StrB [I] : dp[I][j] == dp[I][j-1] + 1
- Delete strA[I] : dp[I][j] == DP [i-1][j] + 1
Select the best.