狗家面经

美国小姐姐,上来就做题了。

判断target字符串是否可以由给定字符串转换得到。转换的规则是:每次转换要变所有的相同字母
比如:abca -> cdec 可以 abca -> abea -> cbec -> cdec

问下为啥26个字母时没有中间值转换呀

请问lz这题是用hashmap来做吗

bfs可以解决把

/* use hash table, map s1 characters to s2, there can be multiple characters mapping to one s1, but not vice versa (this can be used for error detection) */

bool CanConvert(const string & s1, const string & s2){
/* goal: convert s1 to s2 according to the rule /
/
0. MISC */
if(s1.size() != s2.size())return false;

/* 1. prep */
unordered_map<char, char> s1ToS2;

/* 2. key algorithm */
for(int i = 0; i < s1.size(); ++i){

    if(s1ToS2.find(s1) == s1ToS2.end() ){
        s1ToS2[s1] = s2;
    }else if(s2 != s1ToS2[s1]){
        return false;
    }
}
return true;

}

补充内容 (2018-10-14 10:09):
用hashmap,存两个s1和s2(target)的对应关系,一旦s1中的char需要对应到多个s2中的char时,返回错误,全部结束未返回错误的话,返回正确

补充内容 (2018-10-14 10:10):
不知道在楼里写代码合不合适。。。

这个时用二维DP来做吧

重点是考虑target string里有26个字母时,没有中间值转换。
[Java] 纯文本查看 复制代码public boolean canConvert(String s, String p) {
if (s.length() != p.length()) return false;
if (s.equals§) return true;

    Set<Character> set = new HashSet<>();
    for (char c : p.toCharArray()) set.add(c);
    if (set.size() == 26) return false;

    Map<Character, Character> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char temp = s.charAt(i);
        if (!map.containsKey(temp) || map.get(temp) == p.charAt(i)) {
            map.put(temp, p.charAt(i));
        } else {
            return false;
        }
    }
    return true;
}

s1到s2的map是1对1的,
s2到s1的map可以1对多

我感觉其实只需要找到s1里面多个相同的char的位置 比如说‘a’对应位置‘0, 2,3’

在s2的对应位置上的char也都是一样的 比如说对应位置‘0, 2,3’上都是‘c’

就可以了吧

如果在s1中一个char只出现过一次,那么无论是什么都能转换 比如说‘f’在s1中只出现过一次

无论s2是什么都可以在最后转换?

不知道这个思路有没有什么special case

想问一下,每次改变只能改变一组相同的字母,还是可以改变多组不同的,比如
abc
bca
是否可以,假如一次只能改变一个就不行,如果每次改变多个就可以

记得lc里好像有,好像需要从s1变到s2做一次hashmap校对,再从s2变到s1做一次hashmap校对