問題
一意な単語の集合が与えられたとき、リスト中の2つの単語、words[i] + words[j]が回文に連結されるような、すべての異なるインデックスペアを求めなさい。
例1.
c:
[
'abcd',
'dcba',
'lls',
's',
'sssll'
];
b:
[
[ 0x0, 0x1
],
[ 0x1, 0x0
],
[ 0x3, 0x2
],
[ 0x2, 0x4
]
];
bar:
スプライス可能な回文は以下の通りである。['dcbaabcd', 'abcddcba', 'slls', 'llssssll'];例2.
c:
[
'bat',
'tab',
'cat'
];
b:
[
[ 0x0, 0x1
],
[ 0x1, 0x0
]
];
obj:
スプライス可能な回文は以下の通りである。['battab', 'tabbat'];問題解決のためのアイデア
アイデア: 列挙、ハッシュ・テーブル
まず最初に、与えられた単語のリストが一意であるという質問を見て、回文文字列を形成することができる異なるインデックスを持つ単語があるかどうかを判断してみましょうか？
例題では、回文を構成する文字列の長さは必ずしも等しくないことがわかります。そこで、このような2つの文字列a,bがあるとき、a + bが回文であると仮定し、2つの文字列の長さをa_len, b_len.と記録します：
- a_len = b_lenのとき、aはbのフリップでなければなりません；
- a_len＞b_lenのとき、bの長さが小さいので、今回回文を作るには、aの一部がすでに回文でなければなりません。そこでaをa1とa2に分割し、a1の前部分をbの反転とし、a2そのものを回文とします；
- a_len＜b_lenの場合、このケースは上のケースと逆になります。この場合も、bはb1とb2に分割され、b1自体は回文、b2はaの反転です。
上記の分析から、分解された文字列の方が長いことがわかります。そこで今度は、各文字列iを列挙して、それを長い文字列とみなし、i1とi2に分割してみます：
- i1が回文の場合、後続の文字列でi2フリップがあるかどうかを調べることで、上記の3番目のケースを満たします。
- i2が回文文字列の場合、これは上記の2番目のケースに一致しますが、後続の文字列のシーケンスにi1フリップがあるかどうかを調べるには十分です。
ここで、注意しなければならないのは、空文字列の場合です。なぜなら、空の文字列も回文だからです。つまり、上記の分解処理において、文字列iが分解され、文字列i1とi2の一方が空文字列である場合、この状況は実は先に分析した最初のケースと一致します。
つまり、今必要なのは、分割された部分文字列の反転した部分文字列が、与えられた文字列リストに存在するかどうかを判断する方法です。
ここで、ハッシュテーブルを使用して、すべての文字列の反転文字列を格納することを検討することができます。そうすれば、分割された部分文字列を照会るときに、それがハッシュテーブルにあるかどうかを判断するだけで、結果を得ることができます。
具体的なコードの実装は以下の通り。
コードの実装
from typing import List
class Solution:
def palindromePairs(self, words: List[str]) -> List[List[int]]:
def is_palindrome(str, start, end):
"""部分文字列が回文かどうかをチェックする
"""
part_word = str[start:end+1]
return part_word == part_word[::-1]
def find_reversed_word(str, start, end):
"""部分文字列がハッシュテーブルにあるかどうかを調べる
Return:
がハッシュテーブルにない場合、次のように返す。 -1
そうでない場合は、対応するインデックスを返す
"""
part_word = str[start:end+1]
ret = hash_map.get(part_word, -1)
return ret
# 与えられたリストの文字列を反転した文字列を格納するハッシュテーブルを構築する
# キーは反転した文字列で、値は反転する前の文字列のインデックスである。
hash_map = {}
for i in range(len(words)):
word = words[i][::-1]
hash_map[word] = i
res = []
# 文字列を反復処理し、文字列を分割して判定を行う。
for i in range):
word = words[i]
word_len = len(word)
# まず空文字列の有無を判断し、現在の文字列が回文であれば、それを現在の文字列と結合して結果に入れる
if is_palindrome(word, 0, word_len-1) and "" in hash_map and word != "":
res.append([hash_map.get(""), i])
for j in range(word_len):
# まず、割り算の右の部分が回文かどうかを確認する。
if is_palindrome(word, j, word_len - 1):
# 部分文字列の左側部分のフリップがハッシュテーブルにあるかどうかを調べる
left_part_index = find_reversed_word(word, 0, j-1)
# 返されたインデックス値が -1また、それが現在の文字列に対応するインデックスでない場合も同様である。
# 回文を形成できる2つの文字列があることを示し、そのインデックスを結果リストに追加する。
if left_part_index != -1 and left_part_index != i:
res.append([i, left_part_index])
# 原理は上記と同じだが、今度は左の部分が回文かどうかを判断する。
if is_palindrome(word, 0, j-1):
# 正しい部分文字列フリップがハッシュテーブルにあるかどうかを判断する
right_part_index = find_reversed_word(word, j, word_len-1)
if right_part_index != -1 and right_part_index != i:
res.append([right_part_index, i])
return res
words = ["a", ""]
solution = Solution()
solution.palindromePairs(words)
