字符串距离计算

时间复杂度O(n + 26 * 26)

class Solution {
public:
    /**
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return 0;
        }
        //矩阵用来存字符对(i, j)，i代表s1中的字符，j代表s2中的字符，小写字母，矩阵26就够了
        vector<vector<int> > arr(26, vector<int>(26, 0));
        for (size_t i = 0; i < s1.size(); ++i) {
            arr[s1[i] - 97][s2[i] - 97]++;
        }
        int count = 0;
        int m = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < 26; ++j) {
                if (i == j) {
                    count += arr[i][j]; //表示初始就为相同的
                }
                else {
                    //表示此时将i字母变为j字母，但是需要减去初始状态(i, i)匹配对
                    int change = arr[i][j] - arr[i][i]; 
                    m = max(m, change);
                }
            }
        }
        return s1.size() - count - m;
    }
};

class Solution {
public:
    /**
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        int n=S1.length(), a[26][26], s=n, m=0;
        memset(a, 0, sizeof(a));
        for(int i=0;i<n;i++)
            a[S1[i]-'a'][S2[i]-'a']++;
        for(int i=0;i<26;i++)
            for(int j=0;j<26;j++)
                if(i==j)
                    s -= a[i][j];
                else
                    m = max(m, a[i][j]-a[i][i]);

        return s - m;
    }
};

class Solution:
    def GetMinDistance(self , S1 , S2 ):
        dp = [[0] * 26 for i in range(26)]  # 构造一个26*26零矩阵，将a-z对应为0-25的数字
        diff = 0  # 字母不相同的个数，即距离
        num = 0  # 变换字母最多能减少的距离
        for i in range(len(S1)):
            dp[ord(S1[i]) - ord('a')][ord(S2[i]) - ord('a')] += 1
            # ord将字母变为ASCII码对应的数字， 将两个字符串变为一个矩阵表示
            diff += (S1[i] != S2[i])
        for i in range(26):
            for j in range(26):
                num = max(num, dp[i][j] - dp[i][i])  # 注意，在变换的时候，也将对应相同字母变成了不同字母，不要忽略
        return diff - num


a = input().replace('"', '').split(',')
S1 = a[0]
S2 = a[1]
print(Solution().GetMinDistance(S1, S2))

我是用字典记录相同的字符对与不同的字符对

class Solution:
    def GetMinDistance(self , S1 , S2 ):
        # write code here
        N = len(S1)
        dic = {}
        ss=0
        ff = 'ff'
        for i in range(N):
            ss1 = S1[i]
            ss2 = S2[i]
            if ss1!=ss2:
                ss+=1
                if ss1 in dic:
                    if ss2 in dic[ss1]:
                        dic[ss1][ss2]+=1
                    else:
                        dic[ss1][ss2]=1
                else:
                    dic[ss1]={ss2:1}
            else:
                if ss1 in dic:
                    if ff in dic[ss1]:
                        dic[ss1][ff]+=1
                    else:
                        dic[ss1][ff]=1
                else:
                    dic[ss1]={ff:1}
        res=0       
        for ss1 in dic:
            maxv=0
            for ss2 in dic[ss1]:
                if ss2!='ff':
                    if dic[ss1][ss2]>maxv:
                        maxv=dic[ss1][ss2]
            if ff in dic[ss1]:
                maxv-=dic[ss1][ff]
            if maxv>res:
                res=maxv

        return ss-res

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    public int getDistance(String s1, String s2){
        int count = 0;
        for(int i = 0; i < s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i)){
                count++;
            }
        }
        return count;
    }
    
    /*
    思路就是把S1的所有字符依次用a-z依次来替换和S2进行比较
    但是遍历S1来替换的话太复杂了，不如遍历a-z，S1的所有字符一定在a-z里面。
    
    */
    public int GetMinDistance (String S1, String S2) {
        // write code here
        int min = Integer.MAX_VALUE;
        for(char i = 'a'; i <= 'z'; i++){
            for(char j = 'a'; j<='z';j++){
                String tempString = S1.replace(j,i);
                min = Math.min(getDistance(tempString,S2),min);
            }
        }
        return min;
        
    }
}

class Solution {
public:
    /**
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    int GetMinDistance(string S1, string S2) {
        int dis = 0, Max = 0, a[26][26] = {0};
        for (int i = 0; i < S1.length(); i++) {
            if (S1[i] == S2[i]) {
                for (int j = 0; j < 26; j++) if (j != S1[i] - 'a') a[S1[i] - 'a'][j]--;
            }
            else {
                a[S1[i] - 'a'][S2[i] - 'a']++;
                dis++;
            }
        }
        for (int i = 0; i < 26; i++) for (int j = 0; j < 26; j++) Max = max(Max, a[i][j]);
        return dis - Max;
    }
};

def cal(s1, s2):
    dp = [[0] * 26 for _ in range(26)]  # 在某个位置上，有dp[x1][x2]个s1[x1]和s2[x2]
    sums, res = 0, 0
    for i in range(len(s1)):
        dp[ord(s1[i]) - ord('a')][ord(s2[i]) - ord('a')] += 1
        sums += (s1[i] != s2[i])
    return sums - max([dp[i][j] - dp[i][i] for j in range(26) for i in range(26)])