给定两个长度相等的,由小写字母组成的字符串S1和S2,定义S1和S2的距离为两个字符串有多少个位置上的字母不相等。
现在牛牛可以选定两个字母X1和X2,将S1中的所有字母X1均替换成X2。(X1和X2可以相同)
牛牛希望知道执行一次替换之后,两个字符串的距离最少为多少。
"aaa","bbb"
0
牛牛可以将S1中的字符'a'全部替换成字符'b',这样S1就变成了"bbb",那么S1和S2的距离就是0
"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; } };
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 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; } }
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整型 */ // 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; } };
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)])@ see: https://blog.nowcoder.net/n/6e99cd8fabb248d1920ce6931e8fb861