「脸书」在过年中刷题 305 ～ Isomorphic Strings

基本信息

• 题号：305
• 题厂：脸书
• 难度系数：低

判断两个字符串到底是不是 isomorphic，「是」返回 True，「不是」返回 False

s = "egg", t = "add"
返回 True，都是 「122」模式

s = "paper", t = "title"
返回 true，都是 「12134」模式

解题思路

1. 既然要检测，那就要生成一个 pattern 来检测他们一致与否。这里可以想到用 「123.。。。」这种形式来表示 pattern

class Solution:
    # 我们创建一个 helper 函数来帮忙检测。。。
    def helper(self, r: str) -> str:
        pattern = []
        # hashtable 格式为：「字符：出现个数」
        table = {}
        counter = 0

        for i in range(len(r)):
            if r[i] not in table:
                pattern.append(str(counter))
                table[r[i]] = counter
                counter += 1
            else:
                pattern.append(str(table[r[i]]))

        return ",".join(pattern)
    
    # 把字符串输入 helper 获取当前字符串的 pattern
    # 如果 2 者相等，返回 true，否则返回 false
    def isIsomorphic(self, s: str, t: str) -> bool:
        sPattern = self.helper(s)
        tPattern = self.helper(t)

        if sPattern == tPattern:
            return True
        
        return False

除了以上解法，我们也可以适当优化一下。

如果两个字符串格式相同，我们可以创建 2 个 hashmap。key - value 存放 「字符串A 字符 - 对应字符串 B 字符」和「字符串 B 字符 - 对应字符串 A 字符」，从而简化时间复杂度。。。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        sMap = {}
        tMap = {}
        
        # for 循环遍历时，如果当前字符 a，b没有出现在 hashtable 里，就按照 「a ：b」，「b ：a」模式存入绑定；
        # 当字符 a 或 b 再次出现时，看他们的对应值与之前的 hash 表是否对应。如果对应则继续，如果不对应，返回 false
        for i in range(len(s)):
            if s[i] not in sMap and t[i] not in tMap:
                sMap[s[i]] = t[i]
                tMap[t[i]] = s[i]
            elif sMap.get(s[i]) != t[i] or tMap.get(t[i]) != s[i]:
                    return False
        
        return True

Constraints

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s and t consist of any valid ascii character.

考试时，可以向考官讨论两个字符串的长度问题。。。。

测试

• ……

Big O

• 时间复杂度：O（n）
• 空间复杂度：O（n）

总结

• 为了更高的收入，需要研究最优解😭