Skip to content

Latest commit

 

History

History
240 lines (189 loc) · 6.57 KB

README.md

File metadata and controls

240 lines (189 loc) · 6.57 KB
comments difficulty edit_url tags
true
中等
字符串
二分查找
动态规划
滑动窗口
哈希函数

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

English Version

题目描述

给定两个字符串 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 的长度。

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}