小美的字符串匹配度

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();  // 字符串长度
        in.nextLine();
        String s = in.nextLine();
        String t = in.nextLine();
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (charS[i] == charT[i]) {
                count++;
            }
        }

        // 交换之后 可能增加1 可能增加2  这一点比较难判断
        int flag = 0;

        for (int i = 0; i < n; i++) {
            if (charS[i] == charT[i]) { // s和t在i的位置相等的话 就不用交换了
                continue;
            }
            for (int j = i + 1; j < n; j++) { //交换的结果有三种: 0 1 2
                if(charS[j]==charT[j]){
                    continue;
                }
                if (charS[j] == charT[i] && charS[i] == charT[j]) {
                    System.out.println(count + 2); // 达到交换的最大值2了 直接输出即可
                    return;
                } else if (charS[j] == charT[i] || charS[i] == charT[j]) {  // 交换后只有一个相等 flag记录一下
                    flag = 1;
                }
            }
        }

        System.out.println(count + flag);
    }
}

#include <iostream>
using namespace std;

int getAns(int n, string s, string t)
{
    int ans=0;
    string s1  = "", t1 = "";
    for (int i=0; i<n; ++i)
    {
        if (s[i] == t[i]) ++ans;
        else
        {
            s1 += s[i];
            t1 += t[i];
        }
    }
    int m = s1.length();
    int a = 0;
    for (int i=0; i<m; ++i)
    {
        for (int j=0; j<m; ++j)
        {
            if (s1[i] == t1[j])
            {
                a = 1;
                if (s1[j] == t1[i]) return ans+2;
            }
        }
    }
    return ans+a;

}

int main() {
    int n;
    string s, t;
    cin>>n>>s>>t;
    cout<<getAns(n,s,t)<<endl;
    return 0;
}

from collections import defaultdict

n = int(input())
s = input()
t = input()

td = defaultdict(set)

res = 0
count = 0
for sc, tc in zip(s, t):
    if sc == tc: res += 1
    else:
        if count == 2: continue
        if sc in td:
            if tc in td[sc]:
                count = 2
            else:
                count = 1
        
        td[tc].add(sc)
print(res + count)

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        String s1 = sc.next();
        String s2 = sc.next();
        StringBuilder sb1 = new StringBuilder(s1);
        StringBuilder sb2 = new StringBuilder(s2);
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if (sb1.charAt(i)==sb2.charAt(i)) {
                ans++;
                sb1.deleteCharAt(i);
                sb2.deleteCharAt(i);
                len--;
                i--;
            }
        }
        int pos = 0;
        for (int i = 0; i <len ; i++) {
            for (int j = i; j <len ; j++) {
                if (sb1.charAt(i)==sb2.charAt(j)||sb2.charAt(i)==sb1.charAt(j)) {
                    pos = Math.max(1,pos);
                }
                if (sb1.charAt(i)==sb2.charAt(j)&&sb2.charAt(i)==sb1.charAt(j)) {
                    pos = 2;
                    break;
                }
            }
            if (pos==2) break;
        }
        System.out.println(ans+pos);
    }
}

看我的，看我的，时间复杂度是O(n)。

#include <iostream>
using namespace std;
#include <array>
#include <unordered_set>
#include <set>

int main() {
    int n;
    string s;
    string t;
    scanf("%d",&n);
    cin>>s;
    cin>>t;

    int res = 0;
    int w = 0; //权重w的范围[0,2]
    array<int,26> f_s={0}; //统计字符出现的频率
    array<int,26> f_t={0};
    set<pair<char,char>> us;
    for(int i=0;i<n;++i){
        if(s[i] == t[i]){
            ++res;
        }
        else{ //仅不匹配的参与统计
            f_s[s[i]-'a']++;
            f_t[t[i]-'a']++;
            us.emplace(s[i],t[i]);
            if(us.find({t[i],s[i]})!=us.end()){//看看前面是否出现了t[i],s[i]如果，出现了刚好和现在的这一对交换，则增加2匹配度
                w=2;
            }
        }
    }
    for(int i=0;i<26;++i){
       if(f_s[i]>0&&f_t[i]>0){ //如果二者同时都存在相同的字符，那说明是可以让两者的匹配度加1的
            w=max(w,1); //取max的原因是，存在可以成对交换的字符
            break;
       }
    }

    res+=w; //加上权重,记为最终答案
    cout << res <<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

import collections

n = int(input())
s = input().strip()
t = input().strip()

cnt = collections.defaultdict(list)
for i in range(n):
    cnt[t[i]].append(i)

res = 0
for i in range(n):
    if s[i] == t[i]:res += 1

is_legal1, is_legal2 = False, False
for i in range(n):
    if s[i] != t[i]:
        for j in cnt[s[i]]:
            if s[j] == t[i]:
                is_legal2 = True
                break
            elif s[j] != t[j]:
                is_legal1 = True
    if is_legal2:
        break

if is_legal2:
    res += 2
elif is_legal1:
    res += 1
print(res)

import java.util.*;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();
            char[] s = in.nextLine().toCharArray();
            char[] t = in.nextLine().toCharArray();
            int ans = 0;
            int extra = 0;
            // 坑：同一个字符可能在多个位置被需要
            HashMap<Character, List<Integer>> tcharMap = new HashMap<>();
            for (int i = 0; i < n; i++) {
                if (t[i] == s[i]) {
                    ans++;
                } else if (extra != 2) {
                    if (!tcharMap.containsKey(s[i])) {
                        List<Integer> temp = new ArrayList<>();
                        temp.add(i);
                        tcharMap.put(s[i], temp);
                    } else {
                        // 找到新的 s[i] 被需要的位置
                        List<Integer> temp = tcharMap.get(s[i]);
                        // 加入新发现的 所需字符 位置
                        temp.add(i);
 
                    }
                    // 找到所需字符即tcharMap.containsKey(t[i]
                    if (tcharMap.containsKey(t[i])) {
                        List<Integer> temp = tcharMap.get(t[i]);
                        for (int pos : temp) {
                            extra = s[i] == t[pos] ? 2 : 1;
                            if (extra == 2) {
                                break;
                            }
                        }
                    }
                }
            }
            System.out.print(ans + extra);
        }
    }
}

# 使用hash来保存t中字母在s中的所有角标位置信息。



n = int(input())
s=input()
t=input()

def maxRes(s,t):
    res =0 
    ss,tt='',''
    for c1,c2 in zip(s,t):
        if c1 ==c2:
            res+=1
        else:
            ss+=c1
            tt+=c2
    return res,ss,tt

res,s,t = maxRes(s,t)
c2i={}
for i,c in enumerate(s):
    if c not in c2i:
        c2i[c]=[]
    c2i[c].append(i)
eps =0
for i in range(len(t)):
    if t[i] not in c2i:
        continue
    if eps ==0:
        eps=1
    indices_s=c2i[t[i]]#s中ti出现的角标
    for index_s in indices_s:
        if t[index_s] in c2i and i in c2i[t[index_s]]:
            res+=2
            print(res)
            exit()

print(res+eps)

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;
    }
}

import java.util.Scanner;import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        char[] chars = in.next().toCharArray();
        char[] chart = in.next().toCharArray();
        Map<Character, Set<Character>> map = new HashMap<>();
        int res = 0 ;
        int change = 0;
        for (int i = 0; i < n; i++) {
            if (chars[i] == chart[i])res++;
            else {
                Set<Character> set = map.getOrDefault(chart[i], new HashSet<>());
                set.add(chars[i]);
                map.put(chart[i], set);
                if (map.containsKey(chars[i])) {
                    change = Math.max(change, 1);
                    set = map.get(chars[i]);
                    if (set.contains(chart[i])) {
                        change = Math.max(change, 2);
                    }
                }
            }
        }
        System.out.println(res + change);
    }
}

import java.util.*;

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();
        System.out.println(max(s.toCharArray(), t.toCharArray(), n));
    }

    private static int max(char[] s, char[] t, int n) {
        int same = 0;
        int count = 0;
        //只包含小写字母
        List<Integer>[] pre = new List[26];
        Arrays.setAll(pre, value -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            if (s[i] == t[i]) {
                same++;
            } else {
                //交换后最多加2
                if (count < 2) {
                    //看t[i]在s的[0, i-1]是否出现过
                    for (int j : pre[t[i] - 'a']) {
                        if (s[i] == t[j]) {
                            count = 2;
                            break;
                        } else {
                            count = 1;
                        }
                    }
                    pre[s[i] - 'a'].add(i);
                }
            }
        }
        return same + count;
    }
}

借鉴大佬的代码

def sol(n,s1,s2):
    """
        三种交换情况：不交换，交换一个，交换两个
    """
    res_all = [] # 保存剩余不匹配数组
    res_s1 = [] # 保存剩余不匹配的s1数组
    is2Changed,is1Changed = False,False
    idx = 0
    for i in range(n):
        if s1[i] == s2[i]:
            idx += 1
        else:
            # 注意s1和s2的顺序，如果能+2则代表存在 [s2[i],s1[i]] = [s1[i],s2[i]]
            if [s2[i],s1[i]] in res_all and not is2Changed:
                # 交换两个
                idx += 2
                is2Changed = True
            # 如果能+1则代表res_s1中存在s2[i] 
            elif s2[i] in res_s1:
                is1Changed = True
            else:
                res_all.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()
        s2 = input()
        ans = sol(n,s1,s2)
        print(ans)
    except:
        break

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    const length = await readline();
    // Write your code here
    let a_str = await readline();
    let b_str = await readline();
    let max_match = 0;
    a_str = a_str.split("");
    b_str = b_str.split("");
    for (let i = length - 1; i >= 0; i--) {
        if (a_str[i] === b_str[i]) {
            a_str.splice(i, 1);
            b_str.splice(i, 1);
            max_match += 1;
        }
    }
    for (let i = 0; i < a_str.length; i++) {
        if (b_str.includes(a_str[i])) {
            max_match += 1;
            break;
        }
    }
    outer: for (let i = 0; i < a_str.length; i++) {
        for (let j = 0; j < b_str.length; j++) {
            const equal_str = a_str[i] === b_str[j];
            const after_equal_str = b_str[i] === a_str[j];
            if (equal_str && after_equal_str) {
                max_match += 1;
                break outer;
            }
        }
    }
    console.log(max_match);
})();

#include <stdio.h>

int main() {
    int length = 0, m = 0, n = 0;
    char temp;
    scanf("%d", &length);
    char s[length + 1], t[length + 1];
    scanf("%s", s);
    scanf("%s", t);
    for (int k = 0; k < length; ++k) {  // 先对比一次
        if (s[k] == t[k]) {
            ++n;
        }
    }
    for (int i = 0; i < length; ++i) {
        for (int j = 0; j < length; ++j) {
            if (i == j) break;  // 保证被修改过
            temp = s[i];    // 修改一次
            s[i] = s[j];
            s[j] = temp;
            for (int k = 0; k < length; ++k) {  // 对比
                if (s[k] == t[k]) {
                    ++m;
                }
            }
            n = m > n ? m : n;
            m = 0;
            temp = s[i];    // 还原
            s[i] = s[j];
            s[j] = temp;
        }
    }
    printf("%d", n);
    return 0;
}

public class Question2 {
    /**
     * 思路分析：
     * 利用动态规划完成
     * dp[i][j]：表示以s[0-i] 与 t[0-j] 最大匹配度
     *     i表示字符串s的结束位置；
     *     j表示字符串t的结束位置
     * dp[i][0]:
     *     此时只要s[i] = t[0]，则 dp[i][0] = 1；否则为 0；
     *     例如：s = "ababc" t="caabb"
     *     s[0]、s[1]、s[2]、s[3] != 'c',即 ！=t[0]
     *     所以a、ab、aba、abab与 c 最大匹配度为 0；
     *     因为s[4] = c
     *     所以ababc 与 c 最大匹配度为 1；即dp[4][0] = 1
     * dp[0][j]与 dp[i][0] 同理；
     * dp[i][j] 的普遍情况:
     *     s[i] = t[j]，则dp[i][j] = dp[i-1][j-1] + 1；
     *     否则 dp[i][j] = 0
     */
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入n");
        int n = scanner.nextInt();
        scanner.nextLine();
        System.out.println("请输入s");
        String s = scanner.next();
        System.out.println("请输入t");
        String t = scanner.next();
        scanner.close();
        int res = process(s,t);
        System.out.println("最大匹配度为： " + res);

    }

    public static int process(String s,String t){
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        int res = -1;//记录答案


        int[][] dp = new int[sc.length][tc.length];

        //填写第一列：dp[i][0]
        for (int i = 0; i < dp.length; i++) {
            if (sc[i] == tc[0]){
                dp[i][0] = 1;
                res = 1;
            }
        }

        //填写第一行：dp[0][j]
        for (int j = 1; j < dp[0].length; j++) {
            if (sc[0] == tc[j]){
                dp[0][j] = 1;
                res = 1;
            }
        }

        /*
            dp[i][j] 的普遍情况:
                s[i] = t[j]，则dp[i][j] = dp[i-1][j-1] + 1；
                否则 dp[i][j] = 0
         */
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (sc[i] == tc[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = Math.max(res,dp[i][j]);
                }else {
                    dp[i][j] = 0;
                }
            }
        }

        return res;


    }
}