205. Isomorphic String.md

##205 - Hash Table

Given two string s and t, determine if they are isomorphic

Input: s = "egg", t = "add"
Output: true

Input: s = "foo", t = "bar"
Output: false

# O(n^2) complexity
class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        d1, d2 = {}, {}
        for i in range(len(s)):
            if s[i] in d1:
                d1[s[i]] = d1[s[i]] + [i]
            else:
                d1[s[i]] = [i]
        for i in range(len(t)):
            if t[i] in d2:
                d2[t[i]] = d2[t[i]] + [i]
            else:
                d2[t[i]] = [i]
    	return sorted(d1.values()) == sorted(d2.values())

# O(n) complexity
class Solution(object):
    def isIsomorphic(self, s, t):
        d1, d2 = {}, {}
        for v, w in zip(s, t):
            if (v in d1 and d1[v] != w) or (w in d2 and d2[w] != v):
                return False
            d1[v] = w
            d2[w] = v
        return True