Leetcode 【537、890、1016】

题目描述：【String】537. Complex Number Multiplication

解题思路：

计算两个复数相乘，先将两个复数的实数和虚数部分分别提取出来，然后按照复数的运算规则分别计算结果的实数和虚数部分，最后把结果的两部分拼接起来就能得到答案。

Python3 实现：

class Solution:
    def complexNumberMultiply(self, a: str, b: str) -> str:
        real, comp, ret = [0, 0], [0, 0], [0, 0]
        la, lb = a.split("+"), b.split("+")
        real[0], real[1] = int(la[0]), int(lb[0])  # 实数部分
        comp[0], comp[1] = int(la[1][:-1]), int(lb[1][:-1])  # 虚数部分
        ret[0] = real[0] * real[1] - comp[0] * comp[1]
        ret[1] = real[0] * comp[1] + real[1] * comp[0]
        return str(ret[0]) + "+" + str(ret[1]) + "i"  # 拼接结果

---

题目描述：【String】890. Find and Replace Pattern

解题思路：

这道题意思是给一个模式串，需要从字典中找到和模式串相同类型的单词（模式串和字典中的单词长度相同）。

初步的想法是对于一个单词 word 和模式串 pattern，先遍历 word 中的每个字符，建立一个 pattern 中每个字符到 word 中每个字符的映射关系，比如 pattern = "abb"，word = "chh"，我们可以建立 {'a':'c', 'b': 'h'}；如果 word = "fpk"，我们可以建立 {'a':'f', 'b':'k'} （'b': 'p' 被 'b':'k' 覆盖了）。建立好映射关系后，我们再遍历一遍 word 中的每个字符，如果这种映射关系还存在，就说明这个 word 满足 pattern 到 word 的映射。比如上面的 word = "chh" 满足，但是 word = "fpk" 就不满足，因为 'b' 映射到了 'k'，而不是 'p'。

但是这样做有一个问题：比如 pattern = "abb"，word = "ccc"，我们建立的 pattern 到 word 的映射关系是 {'a':'c', 'b':'c'}，然后我们再遍历 word 中的每个字符，这种映射关系还是满足的。但是实际上，'a' 和 'b' 不能映射到同一个字符，换句话说，从 word 到 pattern 的映射也要满足。因此，按照上述做法，我们再建立一个 pattern 到 word 的映射，即 {'c':'b'} （'c':'a' 被 'c':'b' 覆盖了）。这时，我们再遍历 word 中的每个字符，发现 pattern = "abb" 就不满足，因为 'c' 映射到了 'b'，而不是 'a'。

因此，我们需要建立 word 和 pattern 双向的映射关系，然后再遍历时，要同时满足两个方向的对应。如果不对应，就不满足。

时间复杂度 O(len(words)*len(word))，空间复杂度为 O(len(word))。

Python3 实现：

class Solution:
    def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
        ans = []
        for word in words:
            ptow = dict()  # pattern到word的映射
            wtop = dict()  # word到pattern的映射
            flag = True
            for i in range(len(word)):
                ptow[pattern[i]] = word[i]
                wtop[word[i]] = pattern[i]
            for i in range(len(word)):
                # 两个方向的映射都要保证唯一性
                if ptow[pattern[i]] == word[i] and wtop[word[i]] == pattern[i]:
                    continue
                else:
                    flag = False
                    break
            if flag:
                ans.append(word)
        return ans

print(Solution().findAndReplacePattern(["abc","deq","mee","aqq","dkd","ccc"], "abb"))  # ["mee","aqq"]

---

题目描述：【String】1016. Binary String With Substrings Representing 1 To N

解题思路：

方法1（时间复杂度 O(len(s)*len(s))，空间复杂度 O(N)）：

因为看到 S 的长度为 1000，所以第一种想法很简单，就是将 S 所有的子串找出来，转化为数字，存储在集合中（因为可能重复）。然后，对于 1~N，判断每个数字是不是在集合中，如果不在返回 False，都在返回 True。

Python3 实现：

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        ans = set()
        for i in range(len(S)-1, -1, -1):
            s = 0
            b = 1
            for j in range(i, -1, -1):
                s += int(S[j]) * b  # 字串转化为数字
                b *= 2
                ans.add(s)
        for i in range(1, N+1):  # 各个数字是否在集合中
            if i not in ans:
                return False
        return True

方法2（时间复杂度 O(N)，空间复杂度 O(1)）：

方法 1 必须先计算出 S 中所有字串转化成的数字，然后再去判断 1~N 是否都在。那么，如果 S 很长，而 N 很小，求 S 的所有字串就浪费了很多时间。因此，我们有第二种解题方法，就是我们遍历 1~N，对于每个数字 i，把 i 转化为二进制 s = bin(i)[2:]，然后判断这个二进制字串是否在 S 中。如果 s not in S，直接返回 False。如果所有字串都在，返回 True。 这样做也不用开辟空间。

Python3 实现：

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        for i in range(1, N + 1):
            if bin(i)[2:] not in S:
                return False
        return True

提交后发现，方法 2 时间比方法 1 快了很多。其实，上述代码可以用一行来解决：

class Solution:
    def queryString(self, S: str, N: int) -> bool:
        return all(bin(i)[2:] in S for i in range(1,N+1))

其中， all(iterable) 函数接收一个可迭代的元组或列表，如果都为 True，返回 True，否则返回 False。