跳转至

3135. 通过添加或删除结尾字符来同化字符串 🔒

题目描述

给定两个字符串 initial 和 target，你的任务是通过一系列操作改变 initial 以使它与 target 相同。

在一次操作中，您只能在 initial 字符串开头或结尾添加或删除一个字符。

返回将 initial 变为 target 所需的最小 操作次数。

 

示例 1：

输入：initial = "abcde", target = "cdef"

输出：3

解释：

从 initial 的开头删除 'a' 和 'b' 并添加 'f' 到结尾。

示例 2：

输入：initial = "axxy", target = "yabx"

输出：6

解释：

操作 结果字符串
将 'y' 添加到开头 "yaxxy"
从结尾删除 "yaxx"
从结尾删除 "yax"
从结尾删除 "ya"
将 'b' 添加到结尾 "yab"
将 'x' 添加到结尾 "yabx"

示例 3：

输入：initial = "xyz", target = "xyz"

输出：0

解释：

不需要任何操作，因为字符串已经相等。

 

提示：

  • 1 <= initial.length, target.length <= 1000
  • initial 和 target 只包含小写英文字母。

解法

方法一：动态规划

我们不妨假设字符串 initial 和 target 的长度分别为 \(m\) 和 \(n\)。

根据题目描述，我们只需要求出 initial 和 target 的最长公共子串的长度 \(mx\)，那么我们可以从 initial 中删除 \(m - mx\) 个字符，然后再添加 \(n - mx\) 个字符，即可将 initial 转换为 target，因此答案为 \(m + n - 2 \times mx\)。

我们可以使用动态规划的方法求出 initial 和 target 的最长公共子串的长度 \(mx\)。我们定义一个二维数组 \(f\)，其中 \(f[i][j]\) 表示以 initial[i - 1] 和 target[j - 1] 结尾的最长公共子串的长度。那么我们可以得到状态转移方程：

\[ 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} \]

那么 \(mx = \max f[i][j]\)，最终答案为 \(m + n - 2 \times mx\)。

时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别为字符串 initial 和 target 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minOperations(self, initial: str, target: str) -> int:
        m, n = len(initial), len(target)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        mx = 0
        for i, a in enumerate(initial, 1):
            for j, b in enumerate(target, 1):
                if a == b:
                    f[i][j] = f[i - 1][j - 1] + 1
                    mx = max(mx, f[i][j])
        return m + n - mx * 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int minOperations(String initial, String target) {
        int m = initial.length(), n = target.length();
        int[][] f = new int[m + 1][n + 1];
        int mx = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (initial.charAt(i - 1) == target.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    mx = Math.max(mx, f[i][j]);
                }
            }
        }
        return m + n - 2 * mx;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minOperations(string initial, string target) {
        int m = initial.size(), n = target.size();
        int f[m + 1][n + 1];
        memset(f, 0, sizeof(f));
        int mx = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (initial[i - 1] == target[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    mx = max(mx, f[i][j]);
                }
            }
        }
        return m + n - 2 * mx;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func minOperations(initial string, target string) int {
    m, n := len(initial), len(target)
    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    mx := 0
    for i, a := range initial {
        for j, b := range target {
            if a == b {
                f[i+1][j+1] = f[i][j] + 1
                mx = max(mx, f[i+1][j+1])
            }
        }
    }
    return m + n - 2*mx
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function minOperations(initial: string, target: string): number {
    const m = initial.length;
    const n = target.length;
    const f: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    let mx: number = 0;
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            if (initial[i - 1] === target[j - 1]) {
                f[i][j] = f[i - 1][j - 1] + 1;
                mx = Math.max(mx, f[i][j]);
            }
        }
    }
    return m + n - 2 * mx;
}

评论