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

题目链接

题目描述

小红有一个由小写字母构成的字符串 $s$ 。她每次可以把其中任意一个字母替换成其在字母表中相邻的字母（例如把 'b' 替换成 'a' 或者 'c'，且 'a' 和 'z' 也算相邻）。现在小红还有一个字符串 $t$ ，她想知道，最少需要替换多少次，使得字符串 $s$ 能够成为字符串 $t$ 的一个子串。

输入:

第一行输入一个长度为 $n$ 的字符串 $s$ 。
第二行输入一个长度为 $m$ 的字符串 $t$ ( $n \le m$ )。

输出:

一个整数，表示最少需要的替换次数。

解题思路

这个问题的核心是找到一个最优的对齐方式，使得将字符串 $s$ 变换为字符串 $t$ 的某个子串所需的成本最低。

理解变换成本: 题目中提到，每次可以将一个字母替换为其“相邻”的字母。一个关键点是，这是一个循环的字母表，即 'a' 和 'z' 是相邻的。因此，从一个字符 $c_1$ 变换到另一个字符 $c_2$ 的成本（最少替换次数），是它们在循环字母表上的最短距离。这个距离可以表示为 $\min(|c_1 - c_2|, 26 - |c_1 - c_2|)$ 。例如，从 'a' 变到 'y'，直接走是 abs('a' - 'y') = 24 次，但反向走（'a' -> 'z' -> 'y'）只需要 2 次，所以成本是 2。
滑动窗口: 既然要让 $s$ 成为 $t$ 的子串，那么修改后的 $s$ 必须与 $t$ 中一个长度为 $n$ （即 $s$ 的长度）的子串完全相同。我们可以使用“滑动窗口”的方法来解决这个问题。我们将一个长度为 $n$ 的窗口滑过整个字符串 $t$ 。
计算并比较: 对于窗口每滑到一个新位置，我们就得到了一个 $t$ 的子串（记作 $t_{\text{sub}}$ ）。我们计算将 $s$ 的每一个字符逐个变换到 $t_{\text{sub}}$ 对应位置字符的总成本。 $\text{TotalCost} = \sum_{i=0}^{n-1} \min(|s_i - (t_{\text{sub}})_i|, 26 - |s_i - (t_{\text{sub}})_i|)$ 我们遍历所有可能的 $t$ 的子串，计算出每一个对应的总成本，并记录下其中的最小值。
最终结果: 遍历完所有 $m-n+1$ 个窗口后，记录下的全局最小成本就是题目的答案。

这个方法确保了我们考虑了所有可能的目标子串，并且找到了将 $s$ 变换为其中之一的最低成本。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int char_dist(char c1, char c2) {
    int diff = abs(c1 - c2);
    return min(diff, 26 - diff);
}

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

    int n = s.length();
    int m = t.length();
    long long min_cost = -1;

    for (int i = 0; i <= m - n; ++i) {
        long long current_cost = 0;
        for (int j = 0; j < n; ++j) {
            current_cost += char_dist(s[j], t[i + j]);
        }
        if (min_cost == -1 || current_cost < min_cost) {
            min_cost = current_cost;
        }
    }

    cout << min_cost << endl;

    return 0;
}

import java.util.Scanner;
import static java.lang.Math.abs;
import static java.lang.Math.min;

public class Main {
    private static int charDist(char c1, char c2) {
        int diff = abs(c1 - c2);
        return min(diff, 26 - diff);
    }

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

        int n = s.length();
        int m = t.length();
        long minCost = -1;

        for (int i = 0; i <= m - n; i++) {
            long currentCost = 0;
            for (int j = 0; j < n; j++) {
                currentCost += charDist(s.charAt(j), t.charAt(i + j));
            }
            if (minCost == -1 || currentCost < minCost) {
                minCost = currentCost;
            }
        }
        System.out.println(minCost);
    }
}

def char_dist(c1, c2):
    diff = abs(ord(c1) - ord(c2))
    return min(diff, 26 - diff)

s = input()
t = input()

n = len(s)
m = len(t)
min_cost = -1

for i in range(m - n + 1):
    current_cost = 0
    for j in range(n):
        current_cost += char_dist(s[j], t[i+j])
    
    if min_cost == -1 or current_cost < min_cost:
        min_cost = current_cost

print(min_cost)

算法及复杂度

算法：滑动窗口、暴力枚举
时间复杂度： $\mathcal{O}(n \cdot m)$ 。外层循环遍历 $t$ 的所有可能起始点（约 $m$ 次），内层循环计算成本（ $n$ 次）。
空间复杂度： $\mathcal{O}(1)$ 。除了存储输入的字符串外，我们只需要常数级别的额外空间。