# 谷歌 residency 面经题

stringA：“abc”，stringB 是 “aaa”, return true。变换：“abc” -> “aac” -> “aaa”

5 Likes

3 Likes
``````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;
}``````
4 Likes

For example：

``````public boolean canChange(String a, String b) {
if (a == null &amp;&amp; b == null) {
return true;
}
``````
1 Like

1 Like
``````   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)) {
char child = dict.get(parent);
if (chain.contains(child) && parent != child) return false;
parent = child;
}
}
}
return true;
}``````

values.contains 遍历了所有value

n是nodes
e是edge

lol

This problem is now on LeetCode as String Transforms Into Another String