3135. Equalize Strings by Adding or Removing Characters at Ends π
Description
Given two strings initial
and target
, your task is to modify initial
by performing a series of operations to make it equal to target
.
In one operation, you can add or remove one character only at the beginning or the end of the string initial
.
Return the minimum number of operations required to transform initial
into target
.
Example 1:
Input: initial = "abcde", target = "cdef"
Output: 3
Explanation:
Remove 'a'
and 'b'
from the beginning of initial
, then add 'f'
to the end.
Example 2:
Input: initial = "axxy", target = "yabx"
Output: 6
Explanation:
Operation | Resulting String |
---|---|
Add 'y' to the beginning |
"yaxxy" |
Remove from end | "yaxx" |
Remove from end | "yax" |
Remove from end | "ya" |
Add 'b' to the end |
"yab" |
Add 'x' to the end |
"yabx" |
Example 3:
Input: initial = "xyz", target = "xyz"
Output: 0
Explanation:
No operations are needed as the strings are already equal.
Constraints:
1 <= initial.length, target.length <= 1000
initial
andtarget
consist only of lowercase English letters.
Solutions
Solution 1: Dynamic Programming
Let's assume that the lengths of the strings initial
and target
are $m$ and $n$, respectively.
According to the problem description, we only need to find the length $mx$ of the longest common substring of initial
and target
. Then, we can delete $m - mx$ characters from initial
and add $n - mx$ characters to transform initial
into target
. Therefore, the answer is $m + n - 2 \times mx$.
We can use dynamic programming to find the length $mx$ of the longest common substring of initial
and target
. We define a two-dimensional array $f$, where $f[i][j]$ represents the length of the longest common substring ending with initial[i - 1]
and target[j - 1]
. Then, we can get the state transition equation:
$$ f[i][j] = \begin{cases} f[i - 1][j - 1] + 1, & \textit{if } \textit{initial}[i - 1] = \textit{target}[j - 1], \ 0, & \textit{otherwise}. \end{cases} $$
Then $mx = \max f[i][j]$, and the final answer is $m + n - 2 \times mx$.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the lengths of the strings initial
and target
, respectively.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|