谷歌电面

一上来先给段java code把一个string array里的元素+成一个string，问有什么改进
答用stringbuilder。。。

然后正题：

给两个string src和dst，返回能否通过不限次数的转换把src变成dst
规则：
每次转换将src里的所有同一个字符转换成另一个字符，比如: abaca -> e

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

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

traint，不要写完了再改code
对代码整洁要求要很高，尽量简洁
不要因为miss了什么就慌张地写新code补救，先表达清楚，不然面试官会随时质疑你写的每一行代码

贴一下我的解答:

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

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

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

想问下这道题是LC的题么？楼主是怎么做的？

像是find isomorphic string的变种？

提供一个我的想法，把相同character出现的位置算成一个group，比较所有group是否一致。同时查看group size等于26则违反规则。

1. 
   
2. import java.util.*;
   
3. 
   
4. public class ChangeSameCharacter {
   
5.     public static void main(String[] args) {
   
6.         System.out.println(isValidTransfer("abaca", "ebece"));
   
7.         System.out.println(isValidTransfer("abba", "baab"));
   
8.         System.out.println(isValidTransfer("abcdefghijklmnopqrstuvwxyza", "abcdefghijklmnopqrstuvwxyzzb"));
   
9.     }
   
10. 
    
11.     //here we assume all lowercase characters
    
12.     public static boolean isValidTransfer(String src, String dst) {
    
13.         if (src.length() != dst.length()) return false;
    
14.         if (src.equals(dst)) return true;
    
15.         if (!positionMatch(src, dst)) return false;
    
16.         return true;
    
17.     }
    
18. 
    
19. 
    
20.     public static boolean positionMatch(String src, String dst) {
    
21.         Map<Character, List<Integer>> map1 = new HashMap<>();
    
22.         Map<Character, List<Integer>> map2 = new HashMap<>();
    
23.         for (int i = 0; i < src.length(); i++) {
    
24.             char c = src.charAt(i);
    
25.             map1.putIfAbsent(c, new ArrayList<>());
    
26.             map1.get(c).add(i);
    
27. 
    
28.             char c2 = dst.charAt(i);
    
29.             map2.putIfAbsent(c2, new ArrayList<>());
    
30.             map2.get(c2).add(i);
    
31.         }
    
32.         if (map1.size() == 26 || map2.size() == 26) return false;
    
33.         Set<String> positionSet = new HashSet<>();
    
34.         for (char c: map1.keySet()) positionSet.add(map1.get(c).toString());
    
35.         for (char c: map2.keySet()) {
    
36.             if (!positionSet.contains(map2.get(c).toString())) return false;
    
37.             else positionSet.remove(map2.get(c).toString());
    
38.         }
    
39.         return positionSet.size() == 0;
    
40.     }
    
41. }
    
42. 
    

复制代码

补充内容 (2018-9-19 12:18):
这个思路是错的，大家不要看这个。。看lc isomorphic的思路

应该和isomorphic string差不多，区别在于abba -> bbbb这种应该return true？
那么应该比isomorphic还简单，一个map看相同character在另一个string里面对应的字符是不是相同就可以了？

您好！
本帖隐藏的内容需要积分高于 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

贼老窝 发表于 2018-9-16 07:56
是的一个map可以，但是还要考虑借一还一的情况，如果string里面用完了26个字母而又需要一个不同的字母完 ...

那用int array来管理就好了，反正长度已经是固定的了

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

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