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

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