题目思路

思路：思维 + 贪心

当 $len(s) > len(t)$ ，$s$ 中第 $len(t) + 1$ 到 $len(s)$ 这些字符都必须删除。

接下来我们考虑 $[1, min(len(s, len(t)))]$ 的部分。 因为删除只能删除最后一个，所以删除一个字符前，必须删除其后面的所有字符，但是其后面的字符中，可能存在字符和 $t$ 中对应位置的字符相等。

所以最好的操作就是遇到不同的字符则修改。

时间复杂度：$O(n)$

类似题目推荐

这里推荐几道贪心题目

Leetcode

LeetCode上的贪心题，代码随想录总结的非常好了，见 贪心 - 代码随想录

Codefun2000

1. P1091. 米哈游 2023.03.19-第一题-交换字符
2. P1235. 百度 2023.04.15-实习-第一题-字符串前缀
3. P1005. 腾讯 2022.10.16-汽车
4. P1137 美团 2023.04.01-第一题-整理
5. P1077 美团 2023.3.11-第一题-字符串修改
6. P1024 百度 2022.9.13-01反转
7. P1089 美团 2023.3.18.10点-第三题-塔子哥的回文串

代码

C++

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

const int N = 50010;
char s[N], t[N];
int ns, nt;
int n;

void solve() {
    scanf("%s%s", s + 1, t + 1);
    ns = strlen(s + 1), nt = strlen(t + 1);

    int ans = 0;
    // 如果 s 的长度大于 t 的长度，那么从 s[nt + 1] 到 s[ns] 必然都要删除
    if (ns > nt) ans += ns - nt, ns = nt;

    // 如果 s[i] != t[i] ，既然删除（只能修改末字符）和修改的代价相同，不如全部修改
    for (int i = 1; i <= ns; ++i)
        if (s[i] != t[i]) ans += 1;
    printf("%d\n", ans);
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int i = 1; i <= T; ++i) {
        solve();
    }
    return 0;
}

python

T = int(input())
while T > 0:
    s = input()
    t = input()

    ns = len(s)
    nt = len(t)

    ans = 0
    # 如果 s 的长度大于 t 的长度，那么从 s[nt + 1] 到 s[ns] 必然都要删除
    if ns > nt:
        ans += ns - nt
        ns = nt

    for i in range(ns):
        # 如果 s[i] != t[i] ，既然删除（只能修改末字符）和修改的代价相同，不如全部修改
        if s[i] != t[i]:
            ans += 1

    print(ans)

    T -= 1

Java

import java.util.Scanner;

public class Main {

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

        int T = sc.nextInt();
        while (T-- > 0) {
            String s = sc.next();
            String t = sc.next();

            int ans = 0;
            // 如果 s 的长度大于 t 的长度，那么从 s[nt + 1] 到 s[ns] 必然都要删除
            int ns = s.length(), nt = t.length();
            if (ns > nt) {
                ans += ns - nt;
                ns = nt;
            }

            for (int i = 0; i < ns; ++i) {
                // 如果 s[i] != t[i] ，既然删除（只能修改末字符）和修改的代价相同，不如全部修改
                if (s.charAt(i) != t.charAt(i)) {
                    ans += 1;
                }
            }

            System.out.println(ans);
        }
    }

}

Go

package main

import (
    "fmt"
)

const N = 50010

func solve(s, t string) {
    ns, nt := len(s), len(t)

    ans := 0
    // 如果 s 的长度大于 t 的长度，那么从 s[nt + 1] 到 s[ns] 必然都要删除
    if ns > nt {
        ans += ns - nt
        ns = nt
    }

    // 如果 s[i] != t[i] ，既然删除（只能修改末字符）和修改的代价相同，不如全部修改
    for i := 0; i < ns; i++ {
        if s[i] != t[i] {
            ans += 1
        }
    }
    fmt.Printf("%d\n", ans)
}

func main() {
    var T int
    fmt.Scan(&T)
    for i := 0; i < T; i++ {
        var s, t string
        fmt.Scan(&s, &t)
        solve(s, t)
    }
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const N = 50010;

    function solve(s, t) {
        let ns = s.length;
        let nt = t.length;
        let ans = 0;

        // 如果 s 的长度大于 t 的长度，那么从 s[nt + 1] 到 s[ns] 必然都要删除
        if (ns > nt) {
            ans += ns - nt;
            ns = nt;
        }

        // 如果 s[i] != t[i] ，既然删除（只能修改末字符）和修改的代价相同，不如全部修改
        for (let i = 0; i < ns; i++) {
            if (s[i] !== t[i]) {
                ans += 1;
            }
        }

        console.log(ans);
    }

    const T = Number(lines[0]);
    for (let i = 0; i < T; i++) {
        s = lines[i * 2 + 1].trim()
        t = lines[i * 2 + 2].trim()
        solve(s, t);
    }
});