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

土豆炒青椒
·
·
IPFS
刷题自我总结系列,终于在新年中写吐血了。。。

基本信息

  • 题号: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)



总结

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





CC BY-NC-ND 2.0 授权

喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!