[LeetCode] Equalize Strings by Adding or Removing Characters at Ends

3135. Equalize Strings by Adding or Removing Characters at Ends

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int minOperations(string A, string B) {
int n = A.size(), m = B.size(), ma = 0;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(A[i] == B[j]) {
dp[i+1][j+1] = dp[i][j] + 1;
ma = max(ma, dp[i+1][j+1]);
}
}
}
return n + m - 2 * ma;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2024/05/03/PS/LeetCode/equalize-strings-by-adding-or-removing-characters-at-ends/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.