Problem statement

https://leetcode.com/problems/string-transforms-into-another-string/

Solution

The idea is to create graph of connections G between letters. If we have out-degree of some node more than one, we can immedietly return False: we can not make letter a to b in one place and to c in another place. We can have some loops in our graph, like a -> b -> c -> a, in this case we need to be careful. If we have another avaliable symbol, we can use it to resolve conflict. Also if we have pattern like x -> y, z -> y, that is in-degree of some node is more than one, we can do x -> z and now we have avaliable free symbol so we can resolve any conflict. If we do not have pattern like this, it means that all in-degrees and out-degrees are not more than one and we have the following structure of our graph: it is union of several simple loops or paths (oriented). If we have some simple path as one of components, we still can resolve conflicts: because after we resolve this path, we again have free avaliable node. Finally, the only case, when we can not resolve our conflicts if we have union of several loops and these loops cover all 26 symbols of alphabet. And in fact this means that len(set(s2)) == 26.

Complexity

Time complexity is O(n), space complexity is O(26).

Code

class Solution:
    def canConvert(self, s1, s2):
        if s1 == s2: return True
        G = {}
        for i1, i2 in zip(s1, s2):
            if i1 in G and G[i1] != i2: return False
            G[i1] = i2
        return len(set(s2)) < 26