题目大意

给定两个字符串 a 和 b，可以通过删除、插入和替换三种操作将字符串 a 转换为字符串 b。要求计算将字符串 a 转换为字符串 b 的最小代价

思路

该问题类似于编辑距离问题，因此可以考虑使用动态规划来解决。我们定义 dp[i][j] 表示将字符串 a 的前 i 个字符转换为字符串 b 的前 j 个字符的最小代价。

边界情况 当 i 或 j 为 0 时，表示其中一个字符串为空，此时只能通过插入或删除操作将一个字符串转换为另一个。每次插入或删除的代价是 3，因此 dp[i][j] 的值为 (i + j) * 3。

状态转移 状态转移可以分为三种情况：

删除操作：将 a[i] 删除，那么转换成字符串 b 的代价为 dp[i-1][j] + 3。

插入操作：向 a 中插入一个字符 b[j]，那么转换代价为 dp[i][j-1] + 3。

替换操作：将 a[i] 替换为 b[j]，代价为 dp[i-1][j-1] + cal(a[i], b[j])。这里 cal 函数用于计算字符 a[i] 和 b[j] 的替换代价。

计算替换代价 cal cal(a, b) 是用于计算两个字符替换代价的函数，规则如下： $\\$ 1.如果两个字符相同，替换代价为 0； $\\$ 2.如果两个字符都在字符串 s1（"wirel@com"）中，或者都在字符串 s2（"#hfv#gbts"）中，则替换代价为 1； $\\$ 3.如果一个字符在 s1 中，另一个字符在 s2 中，替换代价为 2； $\\$ 4.如果两个字符都不在上述字符集中，替换代价为 3；

题目分析

本题的目标是计算两个基站名字的相似度，可以通过动态规划方法来解决，类似于编辑距离问题。在编辑距离问题中，允许对字符串进行三种操作：增、删、改，每种操作都有不同的代价。题目要求通过最少的操作将一个基站名字转换为另一个基站名字，并输出最小得分。

具体来说：

• 插入一个字符，代价是 3 分；
• 删除一个字符，代价也是 3 分；
• 替换一个字符，替换的代价根据给定的分组规则不同，可能是 1 分、2 分或 3 分。

解决思路

动态规划是解决此类问题的有效方法。我们可以定义 dp[i][j] 表示将字符串 a 的前 i 个字符转换为字符串 b 的前 j 个字符的最小代价。

边界条件

1. 当 i 为 0 时，表示 a 是空字符串，此时只能通过插入操作将 b 的前 j 个字符依次插入进来，代价为 j * 3。
2. 当 j 为 0 时，表示 b 是空字符串，此时只能通过删除操作将 a 的前 i 个字符依次删除，代价为 i * 3。

状态转移方程

对于任意的 dp[i][j]，可以通过三种操作转移得到：

1. 删除操作：将 a[i] 删除，代价为 dp[i-1][j] + 3；
2. 插入操作：向 a 中插入一个字符 b[j]，代价为 dp[i][j-1] + 3；
3. 替换操作：将 a[i] 替换为 b[j]，代价为 dp[i-1][j-1] + cal(a[i], b[j])，其中 cal 是计算替换代价的函数。

替换代价的计算（函数 cal）

• 如果两个字符相同，替换代价为 0；
• 如果两个字符都在组 s1（"wirel@com"）中，或者都在组 s2（"#hfv#gbts"）中，替换代价为 1；
• 如果一个字符在组 s1，另一个字符在组 s2，替换代价为 2；
• 如果两个字符都不在任何组内，替换代价为 3。

动态规划表的初始化

首先，我们将 dp 数组初始化为 (i+j)*3，表示在最坏的情况下，通过删除和插入操作将两个字符串互相转换的代价。

动态规划的填表过程

从 dp[1][1] 开始，通过上面三种操作的最小代价来更新 dp[i][j]。对于每个位置 (i, j)，我们根据前面已经计算好的状态，选择代价最小的一种操作来更新。

复杂度分析

• 时间复杂度：由于我们使用了双重循环填表，每次操作的时间复杂度是常数级别，因此总的时间复杂度为 O(n * m)，其中 n 是字符串 a 的长度，m 是字符串 b 的长度。
• 空间复杂度：使用了一个大小为 2005 x 2005 的二维数组 dp，因此空间复杂度为 O(n * m)。

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
string a, b;
int n, m;
// dp 表，用于存储从 a 到 b 的最小转换代价
int dp[2005][2005];
// 字符集，用于判断字符之间的替换代价
string s1 = "wirel@com", s2 = "#hfv#gbts";

// 计算字符 a 和 b 之间的替换代价
int cal(char a, char b) {
	// 如果两个字符相等，代价为 0
	if (a == b) return 0;
	// 如果两个字符都在 s1 中或都在 s2 中，代价为 1
	if (s1.find(a) != string::npos && s1.find(b) != string::npos) {
		return 1;
	}
	else if (s2.find(a) != string::npos && s2.find(b) != string::npos) {
		return 1;
	}
	// 如果一个字符在 s1 中，另一个字符在 s2 中，代价为 2
	else if (s2.find(a) != string::npos && s1.find(b) != string::npos) {
		return 2;
	}
	else if (s1.find(a) != string::npos && s2.find(b) != string::npos) {
		return 2;
	}
	// 其他情况下，代价为 3
	else {
		return 3;
	}
}

int main() {
	cin >> a >> b;
	n = a.length();
	m = b.length();
	a = ' ' + a;
	b = ' ' + b;
	
	// 初始化 dp 数组
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			// 如果 i 和 j 都为 0，即两个空字符串之间的代价为 0
			if (!i && !j)
				dp[i][j] = 0;
			// 如果 i 为 0，表示将空字符串变为 b 的前 j 个字符，代价为 j * 3（即插入 j 个字符）
			else if (!i)
				dp[i][j] = j * 3;
			// 如果 j 为 0，表示将 a 的前 i 个字符变为空字符串，代价为 i * 3（即删除 i 个字符）
			else if (!j)
				dp[i][j] = i * 3;
			// 否则初始化为 (i+j) * 3
			else
				dp[i][j] = (i + j) * 3;
		}
	}
	
	// 动态规划过程
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			// 计算 dp[i][j] 时，首先考虑插入和删除操作，选择三种操作中的最小值并加上代价 3
			dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i][j]}) + 3;
			// 然后考虑替换操作，使用 cal 函数计算替换代价
			dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + cal(a[i], b[j]));
		}
	}
	
	// 输出将字符串 a 转换为字符串 b 的最小代价
	cout << dp[n][m];
}

python

# 字符集，用于判断字符之间的替换代价
s1 = "wirel@com"
s2 = "#hfv#gbts"

# 计算字符 a 和 b 之间的替换代价
def cal(a, b):
    # 如果两个字符相等，代价为 0
    if a == b:
        return 0
    # 如果两个字符都在 s1 中或都在 s2 中，代价为 1
    if (a in s1 and b in s1) or (a in s2 and b in s2):
        return 1
    # 如果一个字符在 s1 中，另一个字符在 s2 中，代价为 2
    elif (a in s1 and b in s2) or (a in s2 and b in s1):
        return 2
    # 其他情况下，代价为 3
    else:
        return 3

def main():
    # 输入两个字符串
    a = input().strip()
    b = input().strip()

    # 获取字符串的长度
    n = len(a)
    m = len(b)

    # 初始化 dp 数组，大小为 (n+1) x (m+1)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # 初始化 dp 数组
    for i in range(n + 1):
        for j in range(m + 1):
            # 如果 i 和 j 都为 0，即两个空字符串之间的代价为 0
            if i == 0 and j == 0:
                dp[i][j] = 0
            # 如果 i 为 0，表示将空字符串变为 b 的前 j 个字符，代价为 j * 3（即插入 j 个字符）
            elif i == 0:
                dp[i][j] = j * 3
            # 如果 j 为 0，表示将 a 的前 i 个字符变为空字符串，代价为 i * 3（即删除 i 个字符）
            elif j == 0:
                dp[i][j] = i * 3
            # 否则初始化为 (i+j) * 3
            else:
                dp[i][j] = (i + j) * 3

    # 动态规划过程
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 计算 dp[i][j] 时，首先考虑插入和删除操作，选择三种操作中的最小值并加上代价 3
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i][j]) + 3
            # 然后考虑替换操作，使用 cal 函数计算替换代价
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + cal(a[i - 1], b[j - 1]))

    # 输出将字符串 a 转换为字符串 b 的最小代价
    print(dp[n][m])

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class Main {
    static String s1 = "wirel@com";  // 用于判断字符替换代价的字符集 s1
    static String s2 = "#hfv#gbts";  // 用于判断字符替换代价的字符集 s2
    static int[][] dp = new int[2005][2005];  // dp 数组，存储最小转换代价

    // 计算字符 a 和 b 之间的替换代价
    public static int cal(char a, char b) {
        // 如果两个字符相等，代价为 0
        if (a == b) return 0;
        // 如果两个字符都在 s1 中或都在 s2 中，代价为 1
        if (s1.indexOf(a) != -1 && s1.indexOf(b) != -1) {
            return 1;
        } else if (s2.indexOf(a) != -1 && s2.indexOf(b) != -1) {
            return 1;
        }
        // 如果一个字符在 s1 中，另一个字符在 s2 中，代价为 2
        else if (s2.indexOf(a) != -1 && s1.indexOf(b) != -1) {
            return 2;
        } else if (s1.indexOf(a) != -1 && s2.indexOf(b) != -1) {
            return 2;
        }
        // 其他情况下，代价为 3
        else {
            return 3;
        }
    }

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

        // 输入两个字符串
        String a = sc.nextLine();
        String b = sc.nextLine();

        int n = a.length();
        int m = b.length();

        // 初始化 dp 数组
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 如果 i 和 j 都为 0，即两个空字符串之间的代价为 0
                if (i == 0 && j == 0) {
                    dp[i][j] = 0;
                }
                // 如果 i 为 0，表示将空字符串变为 b 的前 j 个字符，代价为 j * 3（即插入 j 个字符）
                else if (i == 0) {
                    dp[i][j] = j * 3;
                }
                // 如果 j 为 0，表示将 a 的前 i 个字符变为空字符串，代价为 i * 3（即删除 i 个字符）
                else if (j == 0) {
                    dp[i][j] = i * 3;
                }
                // 否则初始化为 (i+j) * 3
                else {
                    dp[i][j] = (i + j) * 3;
                }
            }
        }

        // 动态规划过程
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 计算 dp[i][j] 时，首先考虑插入和删除操作，选择三种操作中的最小值并加上代价 3
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i][j]) + 3;
                // 然后考虑替换操作，使用 cal 函数计算替换代价
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + cal(a.charAt(i - 1), b.charAt(j - 1)));
            }
        }

        // 输出将字符串 a 转换为字符串 b 的最小代价
        System.out.println(dp[n][m]);
    }
}

题目内容

在无线通信中，每一个基站都会有一个名字，一般同一个区域的基站名字会比较相近，可以通过判断两个基站名字相似程度来识别它是否在同一区域。通过基站间的名字字符串之间转换，来判断两个基站名字的相似度。字符之间的转换只有$3$种操作(增，删，改):

$1$、增:插入一个字符;

$2$、删:删除一个字符;

$3$、改: 替换一个字符;

并且以上$3$种操作分别对应不同的打分项，得分越低，说明相似度越高。

$1$)增 $3$分; $2$) 删 $3$分; $3$)替换，字符在以下两分组内同一组的得$1$分，分别在两个组的得$2$分，其他得$3$分

组$1${$'w', 'i, 'r', 'e','l, '@', 'c', 'o','m'$}

组$2${$'h,'f', 'v',$'#',$'g', 'b', 't', 's'$}

给定两个无线基站名字，请识别出相似度(即字符转换操作的最低得分)。

输入描述

输入两个名字字符串

注:字符串长度范围[1,2000]。

输出描述

输出两者之间的相似度

样例1

输入

chu
xu		

输出

6

说明

基站名字$1$为“$chu$"，基站名字2“$xu$”，进行这两个基站名字间的字符转换步骤:

第$1$步$c$替换为$x: chu -> xhu$，$c$在组$1$内，$x$不在，所以得分$3$

第2步 $h$删除: $xhu -> xu$，得分$3$

总得分为$6$，所以相似度为$6$，输出$6$

样例2

输入

jinhailu
jinzhanglu

输出

8

说明

基站名字$1$为“$jinhailu$"，基站名字$2$“$jinzanglu$"，进行这两个基站名字间的字符转换步骤:

路径$1$:

第$1$步 $h$替换为$z:jinhailu -> jinzailu$，$h$在组$2$，$z$不在，所以得分为$3$

第$2$步 $i$替换为$n$:$jinzailu -> jinzanlu$，$i$在组$1$，$n$不在，所以得分为$3$

第$3$步 插入$g:jinzanlu -> jinzanglu$，得分为$3$

总得分为$7$

路径$2$:

第$1$步 $h$替换为$z:jinhailu -> jinzailu$,$h$在组$2$，$z$不在，所以得分为$3$

第$2$步 插入$n:jinzailu -> jinzanilu$，插入操作得分为$3$

第$3$步 $i$替换为g:$jinzanilu -> jinzanglu$，$i$在组$1$，$g$在组$2$，所以得分为$2$

总得分为$8$

所以路径$2$，得分少，选择路径$2$，输出$8$