一道谷歌面经 “字符串转换”/transision 个人总结

要送hc了攒个人品顺便回馈地里。为了方便大家看到题目之后搜索解答，在title里加上了“字符串转换面经”跟lintcode里一道类似题目1580 transition string的名字。虽然我并没有在onsite里遇到这道题目，但是在准备面经的过程中能感觉到这道题目至少对我这种水平差的人来说不太好理解。
加上follow up跨越的层级挺大的，很难一步到位，打算小结一下自己在理解这道题中看过的资料和step by step过程。

看过
https://www.1point3acres.com/bbs/thread-449578-1-1.html
https://www.1point3acres.com/bbs/thread-443299-1-1.html
的题目描述
“给定一个字符串s，问能不能转化成另一个字符串p，条件是每次转换要把所有相同的字母一起变动
例子如: abca(两个a一起变) -> dbcd(变c) -> dbed(变b) -> dced。所以abca能转化成dced，return true”
以及
https://www.1point3acres.com/bbs ... tml?_dsign=0a9ca5eb
中有大神给出的详细证明之后，我个人水平比较差，看了很久才摸索到一点门道。
所以打算写个比较intuitive跟naive一点的理解并把代码贴上，希望能对大家只是急于准备把题目做出来并在45分钟面试过程中能有点内容可讲可问提供点参考。
正确性不足的话希望大家多多包含指教别喷我，毕竟发面经已经不是义务，个人总结就更不是了。

接下来就从最简单case到general开始吧

entry
"莉蔻八就灵及其变种“
我知道这道题目是看一位大神总结的高频面经，当然关键就在这个“及其变种“是怎么变种了
我们从最简单对开始看

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

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

以上，祝大家都能offer多多。

感谢总结，祝好运哈

1. import java.util.*;
   
2. 
   
3. // use any letter (26) to transfrom String a to String b, one time change all one type of letters
   
4. // aacc => bbdd, aacc => bbcc => bbdd
   
5. // abc => bca, must get the help of letters which are not in the input string, abc => bbc => ccc?, abc => ebc => eba => eca => bca
   
6. // thus if all 26 distinct chars are in the 2 input string respectively, no possible ways only if abc...z => abc..z (no need to change)
   
7. class Solution {
   
8.     public boolean solution(String a, String b) {
   
9.         if (a == null || b == null) {
   
10.             return false;
    
11.         }
    
12.         if (a.length() != b.length()) {
    
13.             return false;
    
14.         }
    
15. 
    
16.         Map<Character, Character> map = new HashMap<>();
    
17.         for (int i = 0; i < a.length(); i++) {
    
18.             Character ca = a.charAt(i);
    
19.             Character cb = b.charAt(i);
    
20.             map.putIfAbsent(ca, cb);
    
21.             if (map.get(ca) != cb) {
    
22.                 return false;
    
23.             }
    
24.         }
    
25. 
    
26.         // find cycle, if map.keySet() and map.values() are all 26 distinct characters, and exist map.get(i) != i, which means cycle exist
    
27.         int diff = 0;
    
28.         Set<Character> set = new HashSet<>();
    
29.         for (Character c : map.keySet()) {
    
30.             set.add(map.get(c));
    
31.             // if values() contains 26 distinct characters which means keySet() must contain 26 distinct characters
    
32.             // abcd...z => abcd..z, abcd...z => bbcd...z(only 25), abcd...z => bacd..z
    
33.             // has no redundant letter to do the 'bridge' transition
    
34.             if (map.get(c) != c) {
    
35.                 diff++;
    
36.             }
    
37.         }
    
38. 
    
39.         if (diff > 0 && set.size() == 26) {
    
40.             return false;
    
41.         }
    
42. 
    
43.         return true;
    
44.     }
    
45. 
    
46.     public static void canTransform(String a, String b, boolean result) {
    
47.         Solution s = new Solution();
    
48.         System.out.println(s.solution(a, b) == result);
    
49.     }
    
50. 
    
51.     public static void main(String[] args) {
    
52.         canTransform("abcdefghijklmnopqrstuvwxyz","abcdefghijklmnopqrstuvwxya", true); // z => a, true
    
53.         canTransform("abcdefghijklmnopqrstuvwxya","abcdefghijklmnopqrstuvwxyz", false); // a => a / z, false
    
54.         canTransform("aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz","bbaaccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz", false);// false
    
55.         canTransform("abba","baab", true); // true
    
56.         canTransform("abaca", "ebece", true); // true
    
57.         canTransform("abba","bbbb", true); // true
    
58.         canTransform("abc","cba", true); // true
    
59.         canTransform("aac","abc", false); // false
    
60.         canTransform("abc", "bca", true); // true
    
61.     }
    
62. }
    

复制代码

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

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

想请问一下至少转换的步数要怎么解呢？

betterztt 发表于 2019-1-3 00:04
想请问一下至少转换的步数要怎么解呢？

感觉这种就是BFS，类似 LC 127,  752, 433

betterztt 发表于 2019-1-3 00:04
想请问一下至少转换的步数要怎么解呢？

不好意思回复晚了 求步数你可以看看链接里面大神的证明
因为不在这个true/false 判断的类别里 我就没写了 不然帖子太长
只是想抛砖引玉一下而已
祝好运

感觉context 3有问题，hasloop里循环条件应该是while start in dic and start not in visited？按照你的写法，像s='abc', p='bca'是查不出来环的

楼主我感觉context2是不是有点问题 dabc -> ebca这个应该是有解的吧？intermediate就用ebca这里面的就可以。所以有loop也是可以的

补充内容 (2019-1-23 16:03):
哦不对换一个 edabc  ->  dcbca 这个也是有loop的

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

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

祝楼主好运！