首页 > 试题广场 >

小美的字符串匹配度

[编程题]小美的字符串匹配度
  • 热度指数:4133 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小美有两个长度为n只包含小写字母的字符串st,小美定义“两个字符串的匹配度”为i \in [1,n]s_i = t_i的数量,例如"abacd"和"aabdd"的匹配度就是2。

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

小美想知道,st的最大字符串匹配度是多少?

输入描述:
第一行输入一个整数n(2 \leq n \leq 1000)
第二行输入一个长度为n的字符串s
第三行输入一个长度为n的字符串t


输出描述:
输出一个整数,st的最大匹配度。
示例1

输入

5
ababc
babac

输出

3
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        String t = in.next();

        char[] chars = t.toCharArray();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < chars.length; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[i] == s.charAt(i)) {
                    continue;
                }
                swap(chars, i, j);
                max = Math.max(max, check(chars, s));
                //比较后换回来
                swap(chars, i, j);
            }
        }
         System.out.println(max == Integer.MIN_VALUE ? n : max);
    }

    private static int check(char[] chars, String s) {
        char[] charArray = s.toCharArray();
        int ans = 0;
        for (int i = 0; i < charArray.length; i++) {
            if (chars[i] == charArray[i]) ans++;
        }
        return ans;
    }

    private static void swap(char[] chars, int i, int i1) {
        char t = chars[i];
        chars[i] = chars[i1];
        chars[i1] = t;
    }
}
暴力选手
发表于 2024-08-10 00:42:11 回复(0)