205.md

205. Isomorphic Strings

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/isomorphic-strings/

内容描述

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

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

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

Input: s = "paper", t = "title"
Output: true
Note:
You may assume both s and t have the same length.

解题方案

思路 1 - 时间复杂度: O(N) - 空间复杂度: O(N)

题目已经说了s和t的长度相等了，所以不用考虑

用dictionary记录下对应的映射，但是只能单方面限制，所以我们要同时确保s 和 t 是isomorphic，t 和 s 也是isomorphic

beats 67.95%

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        def isoHelper(s1, s2):
            lookup = {}
            for i, c in enumerate(s1):
                if s2[i] in lookup:
                    if c != lookup[s2[i]]:
                        return False
                else:
                    lookup[s2[i]] = c
            return True
        
        return isoHelper(s, t) and isoHelper(t, s)

或是这种写法，感觉比上面应该用时少，但是实际用时还多一点点，不解

beats 60.35%

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        def isomorphic(m):
            lst = []
            d = {}
            for i in range(len(m)):
                if m[i] not in d:
                    d[m[i]] = i
                lst.append(d[t[i]])
            return lst
        return isomorphic(s) == isomorphic(t)

思路 2 - 时间复杂度: O(N) - 空间复杂度: O(N)

一行版本，beats 99.36%

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return len(set(zip(s,t))) == len(set(s)) == len(set(t))