谷歌电面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

贴一下我的解答:

1. bool check(string a, string b)
   
2. {
   
3.     if (a.size()!=b.size()) return false;
   
4.    
   
5.     unordered_map<char,char>Map;
   
6.     for (int i=0; i<a.size(); i++)
   
7.     {
   
8.         if (Map.find(a[i])==Map.end())
   
9.             Map[a[i]]=b[i];
   
10.         else if (Map[a[i]]!=b[i])
    
11.             return false;
    
12.     }
    
13.    
    
14.     unordered_set<char>SetA;
    
15.     unordered_set<char>SetB;
    
16.     int count = 0;
    
17.     for (int i=0; i<a.size(); i++)
    
18.     {
    
19.         SetA.insert(a[i]);
    
20.         SetB.insert(b[i]);
    
21.         if (Map[a[i]]!=a[i]) count++;
    
22.     }
    
23.     if (SetA.size()==26 && SetB.size()==26 && count>0)
    
24.         return false;
    
25.     else
    
26.         return true;
    
27. }

复制代码

三个判据：
1. 两个字符串大小不一样，返回false
2. 从a->b的单向映射Map出现冲突，返回false
3.两个字符串都有26个字符，且Map不冲突，但是存在Map[x]!=x，说明必定有成环的映射关系．这种情况下，因为无法借助第三变量（26个字母都用完了），所以返回false
其他情况都返回true

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1->2, 2->1 用两个map可以么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. exmaples that return false:
   
2. 1. len(src) != len(dst)
   
3. 2. bbbc -> abec     same index has different value in src and dst
   
4. 3. aabbccdef - z -> bbaaccdef - z  there exist change loop  like aabb -> bbaa
   
5.         but we have already used up all the 26 characters
   
6. 
   
7. def transfer_string(self, src, dst):
   
8.         if src is None or dst is None:
   
9.                 return False
   
10.         if len(src) != len(dst):
    
11.                 return False
    
12.         if src == dst:
    
13.                 return True
    
14. 
    
15.         char_to_char = {}
    
16.         dst_char = set()
    
17.         n = len(src)
    
18.         for i in range(n):
    
19.                 if src[i] not in char_to_char:
    
20.                         char_to_char[src[i]] = dst[i]
    
21.                         dst_char.add(dst[i])
    
22.                 else:
    
23.                         if dst[i] != char_to_char[src[i]]:
    
24.                                 return False
    
25. 
    
26.         if len(char_to_char) == 26 and len(dst_char) == 26:
    
27.                 return False
    
28. 
    
29.         return True

复制代码

楼主有心了，我po一下我的代码
确实是一道看着简单但是思考量还不少的题目
即使觉得明显，也要不断check assumption和constraint

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies