1153. String Transforms Into Another String (String) 20.6.4 Hard

Given two strings str1 and str2 of the same length, 
determine whether you can transform str1 into str2 by doing zero or more conversions.

In one conversion you can convert all occurrences of one character in str1 to any other lowercase English character.

Return true if and only if you can transform str1 into str2.

 

Example 1:

Input: str1 = "aabcc", str2 = "ccdee"
Output: true
Explanation: Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.
Example 2:

Input: str1 = "leetcode", str2 = "codeleet"
Output: false
Explanation: There is no way to transform str1 to str2.
 

Note:

1 <= str1.length == str2.length <= 10^4
Both str1 and str2 contain only lowercase English letters.


Solution: O(n) T and S
class Solution(object):
    def canConvert(self, str1, str2):
        """
        :type str1: str
        :type str2: str
        :rtype: bool
        """
        if len(str1) != len(str2):
            return False
        if str1 == str2:
            return True
        pointer = 0
        transform_map = {}
        while pointer < len(str1):
            if str1[pointer] == str2[pointer]:
                pointer += 1
                continue
            else:
                if str1[pointer] in transform_map:
                    if str2[pointer] != transform_map[str1[pointer]]:
                        return False
                    else:
                        pointer += 1
                        continue
                else:
                    transform_map[str1[pointer]] = str2[pointer]
                    pointer += 1
        return len(set(str2)) < 26                                             # The key here!
        
/*
        此题的对应有以下几个关系:
        1. 一对一，每一个char互相对应转换即可 a->b
        2. 多对一， aabcc,ccdee, a->c, c->e，其实只要有未在target string出现过的char，那么就可以拿来
        作为temp char桥梁，比如 a->g->c这样转换就不会同时影响c->e的转换
        3. 一对多，a->f, a->g 这样是绝对不可能的，因为char会被同时影响
        
        另外还有一种特殊情况就是，source和target的unique char的数量是一样的时候，如果此时是26个
        则说明完全不能转换，因为没有extra的temp char作为转换的桥梁
*/



C++ Version:
class Solution {
public:
    bool canConvert(string str1, string str2) {
        if (str1.size() != str2.size()) {
            return false;
        }
        if (str1 == str2) {
            return true;
        }
        int pointer = 0;
        unordered_map<char, char> transform_map {};
        while (pointer < str1.size()) {
            if (str1[pointer] == str2[pointer]) {
                pointer += 1;
                continue;
            } else {
                if (transform_map.find(str1[pointer]) == transform_map.end()) {
                    transform_map[str1[pointer]] = str2[pointer];
                } else {
                    if (transform_map[str1[pointer]] != str2[pointer]) {
                        return false;
                    }
                }
                pointer ++;
            }
        }
        return set(str2.begin(), str2.end()).size() < 26;
    }
};