小红的字符串修改

[题目链接](https://www.nowcoder.com/practice/66e0054ff6b345afa47bcd4e8ceb72d7)

思路

给定字符串 （长度 ）和字符串 （长度 ），每次操作可以将 中某个字母替换为字母表中相邻的字母（字母表是环形的，即 z 和 a 相邻）。求最少操作次数使 成为 的子串。

关键观察

将字母 变为字母 的最少操作次数为 ，因为字母表首尾相连，可以从两个方向走。

枚举起始位置

成为 的子串，即 等于 的某个长度为 的连续子串。因此枚举 中每个合法起始位置 （），计算将 变成 的总代价：

$$

答案为所有起始位置中代价的最小值。

复杂度

  • 时间复杂度：
  • 空间复杂度：（不计输入存储）

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    int ans = INT_MAX;
    for(int i = 0; i <= m - n; i++){
        int cost = 0;
        for(int j = 0; j < n; 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 n = s.length(), m = t.length();
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <= m - n; i++) {
            int cost = 0;
            for (int j = 0; j < n; 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);
    }
}