题解 | #小红的字符串修改#

题目链接

小红的字符串修改

题目描述

小红有两个由小写字母构成的字符串 $s$ 和 $t$ 。她可以对字符串 $s$ 进行一种操作：将其中任意一个字母替换成其在字母表中的相邻字母（例如 'c' 可以变成 'b' 或 'd'）。每次替换算作一次操作。

现在，小红想知道，最少需要多少次操作，才能使得字符串 $s$ 变成字符串 $t$ 的一个子串。

解题思路

这道题的目标是找到一个最优的对齐方式，使得字符串 $s$ 与字符串 $t$ 的某个子串匹配时，所需的总操作次数最少。

首先，我们要理解“替换成相邻字母”这个操作的成本。将一个字母 char1 替换成 char2，最少需要的操作次数等于它们在字母表中的距离，也就是它们 ASCII 码值之差的绝对值，即 abs(char1 - char2)。

既然要让 $s$ 成为 $t$ 的子串，那么修改后的 $s$ 长度必须和原 $s$ 相同。设 $s$ 的长度为 $|s|$ ， $t$ 的长度为 $|t|$ 。我们可以将 $s$ 与 $t$ 中所有长度为 $|s|$ 的子串进行比较。

我们可以使用一个“滑动窗口”的思路：

创建一个长度为 $|s|$ 的窗口，在字符串 $t$ 上从左到右滑动。
窗口每滑动到一个新的位置，就得到了 $t$ 的一个子串。设这个子串为 sub。
我们计算将 $s$ 变换成 sub 所需的总成本。这个成本是 $s$ 和 sub 中对应位置上所有字符的变换成本之和。即： $Cost = \sum_{i=0}^{|s|-1} \text{abs}(s[i] - \text{sub}[i])$
我们遍历所有可能的窗口位置（即 $t$ 的所有长度为 $|s|$ 的子串），计算出每一个位置的成本，并记录下这些成本中的最小值。
遍历结束后，记录的这个最小值就是最终的答案。

例如，s = "abc", t = "abbc"。 $|s|=3$ 。

窗口在 $t$ 的位置0，子串是 "abb"。成本 = abs('a'-'a') + abs('b'-'b') + abs('c'-'b') = $0 + 0 + 1 = 1$ 。
窗口在 $t$ 的位置1，子串是 "bbc"。成本 = abs('a'-'b') + abs('b'-'b') + abs('c'-'c') = $1 + 0 + 0 = 1$ 。所有可能成本为 $\{1, 1\}$ ，最小值为 $1$ 。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;

    int len_s = s.length();
    int len_t = t.length();
    
    long long min_total_cost = numeric_limits<long long>::max();

    // 滑动窗口遍历t中所有长度为len_s的子串
    for (int i = 0; i <= len_t - len_s; ++i) {
        long long current_total_cost = 0;
        // 计算s和当前t的子串的转换成本
        for (int j = 0; j < len_s; ++j) {
            int diff = abs(s[j] - t[i + j]);
            // 考虑循环字母表的最短距离
            current_total_cost += min(diff, 26 - diff);
        }
        min_total_cost = min(min_total_cost, current_total_cost);
    }

    cout << min_total_cost << '\n';

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();

        int lenS = s.length();
        int lenT = t.length();

        long minTotalCost = Long.MAX_VALUE;

        // 滑动窗口遍历t中所有长度为lenS的子串
        for (int i = 0; i <= lenT - lenS; i++) {
            long currentTotalCost = 0;
            // 计算s和当前t的子串的转换成本
            for (int j = 0; j < lenS; j++) {
                int diff = Math.abs(s.charAt(j) - t.charAt(i + j));
                // 考虑循环字母表的最短距离
                currentTotalCost += Math.min(diff, 26 - diff);
            }
            minTotalCost = Math.min(minTotalCost, currentTotalCost);
        }

        System.out.println(minTotalCost);
    }
}

# 读取输入
s = input()
t = input()

len_s = len(s)
len_t = len(t)

min_total_cost = float('inf')

# 滑动窗口遍历t中所有长度为len_s的子串
for i in range(len_t - len_s + 1):
    current_total_cost = 0
    # 提取t的子串
    sub_t = t[i : i + len_s]
    # 计算s和当前t的子串的转换成本
    for j in range(len_s):
        diff = abs(ord(s[j]) - ord(sub_t[j]))
        # 考虑循环字母表的最短距离
        current_total_cost += min(diff, 26 - diff)
    
    min_total_cost = min(min_total_cost, current_total_cost)

print(min_total_cost)

算法及复杂度

算法：滑动窗口 / 暴力匹配。
时间复杂度：外层循环遍历 $t$ 的所有可能的起始位置，共 $|t| - |s| + 1$ 次。内层循环遍历字符串 $s$ 的所有字符，共 $|s|$ 次。因此，总的时间复杂度为 $O(|s| \cdot (|t| - |s| + 1))$ ，可以近似看作 $O(|s| \cdot |t|)$ 。
空间复杂度：我们只使用了少数几个变量来存储长度、成本和循环计数器，没有使用与输入规模成正比的额外空间，因此空间复杂度为 $O(1)$ 。