Pythonでパターンに一致する単語を見つけて置換する方法

問題の概要

単語のリスト words とパターン pattern が与えられたとき、リストの中からパターンに一致する単語をすべて見つけます。ここで「単語がパターンに一致する」とは、文字同士の一対一の対応付け（置換）p が存在し、パターン内のすべての文字 x を p(x) に置き換えると、その単語と完全に一致することを意味します。

例として、入力が ["abc", "deq", "mee", "aqq", "dkd", "ccc"]、パターンが "abb" の場合を考えてみましょう。このときの出力は ["mee", "aqq"] になります。「mee」も「aqq」も、1文字目と2文字目が異なり、2文字目と3文字目が同じという "abb" の構造を持っているためです。一方、「ccc」は3文字すべてが同一であり、文字の置換では "abb" の構造を作れないため、一致とはみなされません。

解法のアプローチ

この問題を解く鍵となるのは、各単語を「文字の並び方の構造」だけを表す数値列へ変換することです。たとえば "abb"、"mee"、"aqq" はいずれも "122" という同じ構造に変換できます。正規化された表現同士を比較すれば、パターンとの一致判定が簡単に行えます。

具体的には、以下の手順で処理を進めます。

• convert() メソッドを定義する：単語を入力として受け取り、次のロジックで構造を表す文字列を生成します。
• counter := 1、s := 空文字列 で初期化し、まず s に counter の文字列表現を連結します。
• i を 1 から単語の長さ − 1 まで順に処理します。
  • j := i − 1 とし、j が 0 以上である限り以下を繰り返します。
  • word[j] が word[i] と等しければループを抜けます。等しくなければ j を 1 減らします。
  • ループ後、j > −1 であれば s := s + s[j]（既出の文字と同じ番号を付与）、そうでなければ counter を 1 増やし、s := s + counter の文字列表現（新しい番号を付与）とします。
• 最終的な s を返します。

続いて、本体のメソッドは次のような流れになります。

• 空の配列 words_num と result を用意します。
• words の各要素に対して convert() を適用し、結果を words_num に格納します。
• pattern 自身も convert() で変換しておきます。
• words_num の各要素と変換済みパターンを比較し、一致した場合に元の単語を result に追加します。
• result を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        words_num = []
        result = []
        for i in words:
            words_num.append(self.convert(i))
        pattern = self.convert(pattern)
        for i in range(len(words)):
            if words_num[i] == pattern:
                result.append(words[i])
        return result

    def convert(self, word):
        counter = 1
        s = ""
        s += str(counter)
        for i in range(1, len(word)):
            j = i - 1
            while j >= 0:
                if word[j] == word[i]:
                    break
                j -= 1
            if j > -1:
                s += s[j]
            else:
                counter += 1
                s += str(counter)
        return s

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

入力

["abc","deq","mee","aqq","dkd","ccc"]
"abb"

出力

['mee', 'aqq']

まとめ

このアルゴリズムのポイントは、単語そのものではなく「文字の出現パターン」を数値列に正規化して比較する点にあります。これにより、どんな文字の組み合わせでも構造が同じであれば一致と判定できます。計算量は、単語の長さを n、単語の数を m とすると O(m × n²) 程度ですが、各文字の前回出現位置を辞書型で記録すれば O(m × n) まで改善できるため、より長い単語を扱う場合にも応用が利く手法です。