小红的字符串修改

思路

拿到这道题，先想一下核心问题是什么？给你两个字符串 s 和 t，s 比 t 短（或等长），你要把 s 修改成 t 的某个连续子串，每次修改一个字符的代价是字母表上的"最短环形距离"。问最小总代价是多少？

什么叫环形距离？比如 a 到 z 的距离不是 25，而是 1——因为可以从 a 往左绕一步到 z。所以两个字符 c1 和 c2 之间的代价是 min(|c1-c2|, 26-|c1-c2|)。

具体做法

  1. 枚举 t 中所有长度为 |s| 的子串（滑动窗口）
  2. 对每个子串，逐字符和 s 比较，累加环形距离
  3. 取所有窗口中代价最小的那个

就是个暴力滑窗，没什么弯弯绕。数据范围 |s|, |t| <= 1000，双重循环最多 ，随便跑。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s, t;
    cin >> s >> t;
    int ls = s.size(), lt = t.size();
    int ans = INT_MAX;
    // 枚举 t 中所有长度为 ls 的子串
    for(int i = 0; i + ls <= lt; i++){
        int cost = 0;
        for(int j = 0; j < ls; j++){
            int d = abs(s[j] - t[i+j]);
            cost += min(d, 26 - d);  // 环形距离
        }
        ans = min(ans, cost);
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        int ls = s.length(), lt = t.length();
        int ans = Integer.MAX_VALUE;
        // 枚举 t 中所有长度为 ls 的子串
        for (int i = 0; i + ls <= lt; i++) {
            int cost = 0;
            for (int j = 0; j < ls; j++) {
                int d = Math.abs(s.charAt(j) - t.charAt(i + j));
                cost += Math.min(d, 26 - d);  // 环形距离
            }
            ans = Math.min(ans, cost);
        }
        System.out.println(ans);
    }
}

s = input()
t = input()
ls, lt = len(s), len(t)
ans = float('inf')
for i in range(lt - ls + 1):
    cost = 0
    for j in range(ls):
        d = abs(ord(s[j]) - ord(t[i + j]))
        cost += min(d, 26 - d)
    ans = min(ans, cost)
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const s = lines[0].trim();
    const t = lines[1].trim();
    const ls = s.length, lt = t.length;
    let ans = Infinity;
    for (let i = 0; i + ls <= lt; i++) {
        let cost = 0;
        for (let j = 0; j < ls; j++) {
            const d = Math.abs(s.charCodeAt(j) - t.charCodeAt(i + j));
            cost += Math.min(d, 26 - d);
        }
        ans = Math.min(ans, cost);
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度: ，外层枚举起点 ，内层逐字符比较
  • 空间复杂度: ，只用了几个变量

总结

这题就是滑动窗口 + 环形距离计算，没有任何技巧。唯一容易忽略的点是字母表是"环形"的，a 和 z 只差 1 步，不是 25 步。算距离的时候记得取 min(d, 26-d) 就行了。