小美的字符串匹配度

[编程题]小美的字符串匹配度

热度指数：4134 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美有两个长度为 $n$ 只包含小写字母的字符串 $s$ 和 $t$ ，小美定义“两个字符串的匹配度”为 $i \in [1,n]$ 中 $s_i = t_i$ 的数量，例如"abacd"和"aabdd"的匹配度就是2。

现在你可以进行最多一次以下操作:
对于字符串 $t$ ，选择两个索引 $i,j(1 \leq i \lt j \leq n)$ ，交换 $t_i$ 和 $t_j$ 。

小美想知道， $s$ 和 $t$ 的最大字符串匹配度是多少？

输入描述:

第一行输入一个整数
第二行输入一个长度为的字符串。
第三行输入一个长度为的字符串。

输出描述:

输出一个整数，和的最大匹配度。

示例1

输入

5
ababc
babac

输出

算法知识视频讲解

Python

秋招早日上岸

三种交换情况：不交换，交换一个，交换两个

def sol(n,s1,s2):
    """
        三种交换情况：不交换，交换一个，交换两个
    """
    temp,res_s1 = [],[]
    is2Changed,is1Changed = False,False
    sumPss,idx = 0,0
    for i in range(n):
        if s1[i] == s2[i]:
            idx += 1
        else:
            if [s2[i],s1[i]] in temp and not is2Changed:
                # 交换两个
                idx += 2
                is2Changed = True
            elif s2[i] in res_s1:
                is1Changed = True
            else:
                temp.append([s1[i],s2[i]])
                res_s1.append(s1[i])
    # 交换一个
    if is1Changed and not is2Changed:
        idx += 1
    return idx
 
 
while 1:
    try:
        n = int(input())
        s1 = input().strip()
        s2 = input().strip()
        ans = sol(n,s1,s2)
        print(ans)
    except:
        break

发表于 2023-10-21 03:05:22 回复(0)