題目

解題概念

  • 此題簡單來說，就是給定一堆字串 words，確認每個字串是否可以映射成 pattern 的模式，且對應的字母不可重複
    • EX :
      1. word = mee、pattern = aqq :
        • Result : true，因為可推論出 m → a、e → q
      2. word = mn、pattern = aa :
        • Result : false，因為雖然 m → a，但 n 不能對應 a
  • 而在實際執行上，我使用 Hashmap 結構去儲存對應的字母
    • 在做對應時，有一點要特別注意 : 必須要用雙對應 (即使用 2 個 Hashmap)
    • 只用單一對應的反例 : 在做 word = mn、pattern = aa 的對應時，雖然可以找到 m → a，但 n 也會對應 a ，這樣就違反題意
    • 用雙對應的正例 : word = mee、pattern = aqq，則可得出 :
      • word2pattern[m] = a、word2pattern[e] = q
      • pattern2word[a] = w、pattern2word[q] = e

實際寫Code

  • 目標函式 : findAndReplacePattern(words, pattern)

    • Input : words: List[str]、pattern: str
    • Output : List[str]

  • 前置作業 : 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    res = []
    # 針對每個字串
    for word in words : 

        # 若該字串符合 pattern，則加入到 res 中
        if self.match(word, pattern):
            res.append(word)

    return res

  • 主要處理對應之程式碼 : 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    def match(self, word, pattern) :

        # 建立雙對應之 Hashmap
        word2pattern = {}
        pattern2word = {}

        # 針對 word 與 pattern 的每個字元
        for i in range(len(word)) : 

            # 取出 word 與 pattern 的一個字元
            w = word[i]
            p = pattern[i]

            # 若 w 不在 word2pattern 中，則將其加入
            if w not in word2pattern : 
                word2pattern[w] = p

            # 若 p 不在 pattern2word 中，則將其加入
            if p not in pattern2word : 
                pattern2word[p] = w

            # 若 「word2pattern中，w的對應不是p」 或 「pattern2word中，p的對應不是w」
            if word2pattern[w] != p or pattern2word[p] != w : 

                # 則回傳 false
                return False

        # 都沒問題的話，則回傳 true
        return True