华为OD机试 - 最长子字符串的长度（Java & JS & Python & C & C++）

题目描述：

给定两个字符串 A 和 B，现要从 A 中删除特定数量的字符，使得结果包含 B 中所有的字符。请找出最小需要删除的字符数量。

输入描述：

输入包含多组测试数据。每组测试数据共两行，第一行代表字符串 A，第二行代表字符串 B。

输出描述：

对于每组测试数据，输出最小需要删除的字符数量。

示例：

输入：

abcde

abcd

输出：

1

解决方案：

这是一个经典的动态规划问题，可以通过维护一个数组来记录到当前位置为止，需要删除的最小字符数。

以下是使用不同语言实现的解决方案：

Java 代码：

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String A = scanner.nextLine();
            String B = scanner.nextLine();
            System.out.println(minDeletion(A, B));
        }
        scanner.close();
    }
 
    private static int minDeletion(String A, String B) {
        int m = A.length();
        int n = B.length();
        int[][] dp = new int[m + 1][n + 1];
 
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }
 
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return m - dp[m][n];
    }
}

JavaScript 代码：

process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk) {
    const lines = chunk.trim().split('\n');
    const A = lines[0];
    const B = lines[1];
    process.stdout.write(minDeletion(A, B) + '\n');
});
 
function minDeletion(A, B) {
    let m = A.length;
    let n = B.length;
    let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
 
    for (let i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }
 
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (A[i - 1] === B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return m - dp[m][n];
}

Python 代码：

import sys
 
def minDe