首页 > 试题广场 >

字符串距离计算

[编程题]字符串距离计算
  • 热度指数:3876 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个长度相等的,由小写字母组成的字符串S1和S2,定义S1和S2的距离为两个字符串有多少个位置上的字母不相等。
现在牛牛可以选定两个字母X1和X2,将S1中的所有字母X1均替换成X2。(X1和X2可以相同)
牛牛希望知道执行一次替换之后,两个字符串的距离最少为多少。

示例1

输入

"aaa","bbb"

输出

0

说明

牛牛可以将S1中的字符'a'全部替换成字符'b',这样S1就变成了"bbb",那么S1和S2的距离就是0
示例2

输入

"aabb","cdef"

输出

3

说明

一种可行的方案是将S1中的字符'a'全部替换成字符'c',那么S1变成了"ccbb",和S2的距离是3

备注:

S1和S2中的字母均为小写字母
时间复杂度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;
    }
};

发表于 2020-05-02 16:50:56 回复(0)
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;
    }
};

发表于 2020-08-07 00:48:35 回复(0)
将两个字符串用26*26的矩阵表示,注意在变换字母的时候,对应字母的相同字母会变成不同字母,要减去这部分,才是能减少的最多距离。
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))


发表于 2020-05-25 18:44:46 回复(0)

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

现在限定为小写字母其实可以用[26]*[26]这样的矩阵去记录,会快一些
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


发表于 2020-04-11 17:39:56 回复(0)
时间复杂度O(26*26*N)
import java.util.*;

public class Solution {
    /**
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    // 字符串距离计算
    public int GetMinDistance (String S1, String S2) {
        if(S1==null||S2==null||S1.length()!=S2.length()) throw new IllegalArgumentException();
        char[] s1=S1.toCharArray(),s2=S2.toCharArray();
        int ans=Integer.MAX_VALUE;
        for(char x1='a';x1<='z';++x1){
            for(char x2='a';x2<='z';++x2){
                int tmp=0;
                for(int i=0;i<s1.length;++i){
                    if(s1[i]==x1){
                        s1[i]=x2;//替换
                        if(s1[i]!=s2[i]) ++tmp;//计算距离
                        s1[i]=x1;//恢复
                    }else{
                        if(s1[i]!=s2[i]) ++tmp;//计算距离
                    }
                }
                ans=Math.min(ans,tmp);
            }
        }
        return ans;
    }
}


发表于 2020-03-19 17:44:59 回复(0)
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;
        
    }
}


编辑于 2021-03-12 15:27:35 回复(0)
暴力感觉也能过,最差好像是 26*26*5*10^4,不会TLE:
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 计算最少的距离
     * @param S1 string字符串 第一个字符串
     * @param S2 string字符串 第二个字符串
     * @return int整型
     */
    // O(n)
    int CalDis(string& s1, string& s2, char x1, char x2) {
        int cnt = 0;
        for (int i = 0; i < s1.size(); ++i) {
            if (s1[i] == x1 && s2[i] == x2) continue;
            if ((s1[i] == x1 && s1[i] == s2[i]) || s1[i] != s2[i]) cnt++;
        } 
        return cnt;
    }
    
    int GetMinDistance(string S1, string S2) {
        // write code here
        map<char, int> m1, m2;
        for (auto c : S1) m1[c]++;
        for (auto c : S2) m2[c]++;
        
        int res = INT_MAX;
        for (auto it : m1) {
            for (auto it2 : m2) {
                if (it.first == it2.first) continue;
                res = min(res, CalDis(S1, S2, it.first, it2.first));
            }
        }
        return res;
    }
};


发表于 2021-03-11 14:05:59 回复(0)
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;
    }
};

发表于 2020-07-26 14:51:41 回复(0)
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)])
@ see: https://blog.nowcoder.net/n/6e99cd8fabb248d1920ce6931e8fb861
编辑于 2020-05-16 11:56:55 回复(0)
function GetMinDistance( S1 ,  S2 ) {
    var arr = []
    var count = 0
    var str =''
    for(let i =0; i<S1.length; i++){
        if(S1[i]!== S2[i]){
            count ++;
            arr.push(S1[i]+S2[i]);
        } 
        else{
            str+=S1[i]
        }
    }
    
    var a= [];
    if(count>0){
        var set =[...new Set(arr)];
        for(let j=0; j<set.length;j++){
            let reduce = 0,
                same = 0,
                obj = {}
            arr.forEach((item,key)=>{
                if(item === set[j]){
                    reduce++;
                }
            })
            let regex = new RegExp(set[j][0], 'g'); // 使用g表示整个字符串都要匹配
            let result = str.match(regex);
            same = result!==null ? result.length : 0
            obj.key = reduce
            obj.value = same
            a.push(obj)
        }
    }
    a.sort((a,b)=> (b.key-b.value)-(a.key-a.value) )
    
    return count - (a[0].key-a[0].value);
}
发表于 2020-04-06 08:06:23 回复(0)