String Transforms Into Another String

Problem Id: 1153 Difficulty: Hard Tag: Graph


Intuition

Actually I used one of the brute force to solve this hard problem.

The key point of this solution is that, all c in str1 mast map to the same letter in str2. So we can set this mapping when first time see c in str1 And them check it later we see c.

One edge case is that, if all 26 letters have been used, then there is no way to transform str1 to str2 if there are 26 different letters in str2. Because the transforms should be down one by one.

Solution


class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        mapping = {}
        for c1, c2 in zip(str1, str2):
            if c1 not in mapping:
                mapping[c1] = c2
            elif mapping[c1] != c2:
                return False
        if len(set(mapping.values())) == 26:
            for c in string.ascii_lowercase:
                if mapping[c] != c:
                    return False
        return True