Google Onsite 没拿到offer，但是给了residency的加面面试，是一轮hangout面试。
面试官是个白人小姐姐，她说她自己就是residency转正的，还以为题目不会太难，结果非常难！
题目是：
给一个string A，比如 “aba”，要求通过不断地 replace 某个 character (同一个character必须一起替换)，若能变成 string B，则return true，否则 return false。
比如：stringA：“aba”，stringB 是 “cac”，则return true，变换：“aba” -> “cbc” -> “cac” 。
再举2个
：
stringA：“abc”，stringB 是 “aaa”, return true。变换：“abc” -> “aac” -> “aaa”
但是 “abc” 是没法到 "cba"的，return false。
我到现在都没思路，求问大神们有没有好的思路 
我当时用isomorphic string 的思路做，基本都对了。
然后面试官说“abc” 是没法到 "cba"的。
现在想想可以 abc -> dbc -> dba -> cba，其实是可以的。唉，不知道为啥面试官这么说。面试官错了吗。
这个正好是我的onsite题。abc 不能转成 cba是有前提条件的，是字母选择的范围不能超出原有字符里的字母，也就是你的字母要从abc里挑。
补充一下：这道题其中一个挺重要的部分就是和面试官确认可选字母的范围，因为大家默认就是26个字母随便替，abc那么字母范围就是从a到c（前提都小写）如果是abz那情况就大不一样了因为字母范围是a到z 通过这个方式就可以先虑掉一大波情况为false的，比如abc你是无论如何都换不成zbz，因为不在里面。然后再是拓扑排序。
这是一道面经题。
思路是：
建立字符之间的map，比如 abc 到 efg，就是 a->e，b->f，c->g，确认没有conflict，然后把map当作graph的adjacency list，用topological sort检查是否有cycle，如果有环，看是否有多余的字符变量用于解环。
public boolean canChange(String a, String b) {
if(a==null && b==null) {
return true;
}
if(a==null || b==null || a.length()!=b.length()) {
return false;
}
char[] aa = a.toCharArray();
char[] bb = b.toCharArray();
Map<Character, Character> dict = new HashMap<>();
for(int i=0; i<aa.length; i++) {
if(aa[i] == bb[i]) {
continue;
}
if(!dict.containsKey(aa[i])) {
dict.put(aa[i], bb[i]);
}
char curr = aa[i];
for(int j=0; j<aa.length; j++) {
if(aa[j]==curr) {
aa[j] = dict.get(curr);
}
}
if(String.copyValueOf(aa).equals(String.valueOf(bb))) {
return true;
}
}
return false;
}确实还是要遍历一下dict…
文字和代码之间空一行，选中你要format的代码，然后点 “</>” 这个图标。
For example：
public boolean canChange(String a, String b) {
if (a == null && b == null) {
return true;
}
大哥你这代码连"abc", "bca"都返回true啊
嗯， 那个解法确实有bug。但是可以single out这个edge case。如果没有别的edge case，也许是可行的。也就是把这种edge case 单独处理。
public static boolean canChange2(String a, String b) {
if (a == null && b == null) {
return true;
}
if (a == null || b == null || a.length() != b.length()) {
return false;
}
Map<Character, Character> dict = new HashMap<>();
for (int i = 0; i < a.length(); i++) {
char chA = a.charAt(i);
char chB = b.charAt(i);
if (dict.containsKey(chA) && chB != dict.get(chA)) {
return false;
}
dict.put(chA, chB);
}
// dfs
Set<Character> visited = new HashSet<>();
for (char c : dict.keySet()) {
if (!visited.contains(c)) {
char parent = c;
Set<Character> chain = new HashSet<>();
while (dict.containsKey(parent) && !visited.contains(parent)) {
visited.add(parent);
chain.add(parent);
char child = dict.get(parent);
if (chain.contains(child) && parent != child) return false;
chain.add(child);
parent = child;
}
}
}
return true;
}你这个不是 O(n) 了吧
values.contains 遍历了所有value
即使用拓扑排序也是O(n)吧，精确说是 n + e
n是nodes
e是edge
lol
感谢解释，可是还有一点不明白，就是abc到cba这个，这个不成立是因为有环么？a到c到a的环？因为这个例子也没有违反你提出来的超出字母适用范围的情况
感谢解答，可以有个问题，我们为什么要看有没有环呢？面试官这么要求的？
是的环就是a-c-a. 我们在建立有向图的时候，按位来建， 因为最好的情况就是我们按照最终的字符串的字母来替换a换成c b保持不变，c改成a。 只不过因为环的存在a改成c再改第一个字母和第三个字母就连动了。这个时候刚才说的字母范围就起到了作用，因为如果有其他字母存在就可以帮我们解环。比如 abz zba这个例子也是有环，但是范围是a到z所以我们完全可以把a先换成f， z改a ，f再改z 来完成替换所以还是true。