15. 最少前缀操作问题

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐ 中

问题描述

小 U 和小 R 有两个字符串，分别是$S$和$T$，现在小 U 需要通过对$S$进行若干次操作，使其变成$T$的一个前缀。操作可以是修改$S$的某一个字符，或者删除$S$末尾的字符。现在你需要帮助小 U 计算出，最少需要多少次操作才能让$S$变成$T$的前缀。

测试样例

样例 1：

输入：S = "aba", T = "abb"
输出：1

样例 2：

输入：S = "abcd", T = "efg"
输出：4

样例 3：

输入：S = "xyz", T = "xy"
输出：1

样例 4：

输入：S = "hello", T = "helloworld"
输出：0

样例 5：

输入：S = "same", T = "same"
输出：0

解题思路

我们需要找到将字符串 S 变成字符串 T 的前缀所需的最少操作次数。操作可以是修改字符或删除末尾字符。最优解可以通过以下步骤实现：

1. 遍历比较字符：从第一个字符开始，逐个比较 S 和 T 的字符。
2. 计算修改次数：对于每个字符位置，如果 S 和 T 的字符不同，则需要一次修改操作。
3. 处理长度差异：
   • 如果 S 比 T 长，则需要删除多余的字符，操作次数为 S.length - T.length。
   • 如果 S 比 T 短，则只需比较前 S.length 个字符的差异。
4. 综合操作次数：修改次数加上删除次数即为总操作次数。

代码实现

function solution(S, T) {
    let minOperations = Infinity;
    const maxLen = Math.min(S.length, T.length);
    
    // 遍历所有可能的前缀长度
    for (let len = 0; len <= T.length; len++) {
        let operations = 0;
        
        // 计算修改操作次数
        for (let i = 0; i < len; i++) { if (i >= S.length) {
                operations += len - S.length;
                break;
            }
            if (S[i] !== T[i]) {
                operations++;
            }
        }
        
        // 计算删除操作次数
        if (len < S.length) {
            operations += S.length - len;
        }
        
        // 更新最小操作次数
        if (operations < minOperations) {
            minOperations = operations;
        }
    }
    
    return minOperations;
}

function main() {
    console.log(solution("aba", "abb") === 1);    // true
    console.log(solution("abcd", "efg") === 4);   // true
    console.log(solution("xyz", "xy") === 1);     // true
    console.log(solution("hello", "helloworld") === 0); // true
    console.log(solution("same", "same") === 0);  // true
}

main();

代码解释

1. 初始化最小操作次数：minOperations 初始化为一个极大值，用于后续比较。
2. 遍历所有可能的前缀长度：从 0 到 T 的长度，计算每个长度下的操作次数。
3. 计算修改操作次数：
   • 对于每个字符位置，如果 S 和 T 的字符不同，则增加修改次数。
   • 如果 S 比当前前缀长度短，则需要增加字符（但题目不允许插入，所以这种情况不会发生）。
4. 计算删除操作次数：如果 S 比当前前缀长度长，则需要删除多余的字符。
5. 更新最小操作次数：每次计算完当前前缀长度的操作次数后，更新 minOperations。
6. 返回结果：最终返回最小的操作次数。

这个解法的时间复杂度是 O(n * m)，其中 n 是 S 的长度，m 是 T 的长度。由于题目中字符串长度不会太大，这个解法是高效的。

以上关于15. 最少前缀操作问题的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。