私は Manacher のアルゴリズムには詳しくありませんが、効率的なアルゴリズムを考えるのが好きだったので、これに挑戦してみようと思いました。
文字列が回文であるかどうかを判断するアルゴリズムは、私が思いついた種類のように見えるので、関数をそのまま使用することにisPalindromeしましたが、代わりに拡張機能の関数に変更しString、空白の削除を削除しましたこれは、回文決定関数自体ではなく、呼び出し側にある必要があると感じたからです。
extension String {
func isPalindrome() -> Bool {
if length < 2 { return false }
let str = lowercased()
let strArray = Array(str.characters)
var i = 0
var j = strArray.count-1
while i <= j {
if strArray[i] != strArray[j] { return false }
i+=1
j-=1
}
return true
}
}
あなたのpalindromsInStringソリューションを見た後、それは標準的なブルート フォースのように見えますが、シンプルで読みやすいソリューションです。
別のアルゴリズムについての私の最初の考えもかなり力ずくでしたが、まったく異なるアプローチだったので、私はそれをナイーブ ソリューションと呼んでいます。
単純なソリューションの考え方は、元の文字列の部分文字列の配列を作成し、各部分文字列が回文かどうかを確認することです。部分文字列を決定する方法は、可能な限り最大の部分文字列 (元の文字列) から始めて、長さ の 2 つの部分文字列を取得しstring.length-1、string.length-2最後に長さ 2 のすべての部分文字列を取得するまで続けます (部分文字列は無視します)。長さ 1 の文字列は回文にならないと言ったからです)。
つまり、長さ 1 より大きい「test」の部分文字列は次のようになります。
["test"] ["tes", "est"] ["te", "es", "st"]
したがって、これらの各配列をループして、回文であるかどうかを確認し、回文である場合はカウントを増やします。
単純な解決策:
extension String {
var length: Int { return characters.count }
func substringsOfLength(length: Int) -> [String] {
if self.length == 0 || length > self.length { return [] }
let differenceInLengths = self.length - length
var firstIndex = startIndex
var lastIndex = index(startIndex, offsetBy: length)
var substrings: [String] = []
for _ in 0..<differenceInLengths {
substrings.append(substring(with: Range(uncheckedBounds: (firstIndex, lastIndex))))
firstIndex = index(after: firstIndex)
lastIndex = index(after: lastIndex)
}
substrings.append(substring(with: Range(uncheckedBounds: (firstIndex, lastIndex))))
return substrings
}
}
extension String {
func containsAPalindromeNaive(ignoringWhitespace: Bool = true) -> Int {
let numChars = length
if numChars < 2 { return 0 }
let stringToCheck = (ignoringWhitespace ? self.components(separatedBy: .whitespaces).joined(separator: "") : self).lowercased()
var outerLoop = numChars
var count: Int = 0
while outerLoop > 0 {
let substrings = stringToCheck.substringsOfLength(length: outerLoop)
for substring in substrings {
if substring.isPalindrome() {
count += 1
}
}
outerLoop -= 1
}
return count
}
}
このアルゴリズムが遅いことは十分承知していましたが、実際のソリューションの 2 番目のベースラインとして実装したいと考えていました。
私はこのソリューションをスマートソリューションと呼んでいます。これは、文字列内の文字の数と位置を利用するマルチパス ソリューションです。
最初のパスでは、私がキャラクター マッピングと呼ぶものを生成します。文字マッピングは、Characterインデックスの配列に a をマップする辞書です。したがって、文字列を調べて、各文字のインデックスをその文字値の下にキーとして格納されている配列に追加します。
回文は、同じ文字で結ばれた文字列内にのみ存在できるという考えです。したがって、特定の文字のインデックスにある文字列内の部分文字列のみをチェックする必要があります。「tattoo」という単語には、「t」、「a」、「o」の 3 つの異なる文字があります。文字マッピングは次のようになります。
t: [0,2,3]
a: [1]
o: [4,5]
回文は、(0,2)、(2,3)、および (4,5)の間のこの単語にのみ存在できることがわかりました。したがって、3 つの部分文字列(0,2)、(0,3)、(2,3)、および (4,5) のみをチェックする必要があります。したがって、4 つの部分文字列のみをチェックする必要があります。それがアイデアです。特定の文字で予約されている可能性のあるすべての部分文字列をチェックアウトしたら、その文字で始まる他の部分文字列はすべてチェック済みであるため、無視できます。
2 番目のパスでは、文字列内の各文字を調べます。その文字をまだチェックしていない場合は、 forによって生成された順列インデックスのペアを調べます。generateOrderedPairIndexPermutations文字マッピングのインデックスを調べ、部分文字列をチェックしてそれらが回文であるかどうかを確認します。次に、ここで 2 つの最適化を行います。まず、開始文字インデックスと終了文字インデックスの間の距離が 3 未満の場合、それは回文である必要があります (距離 1 はそれらが連続していることを意味し、距離 2 はそれらの間に単一の文字があることを意味します。したがって、回文であることが保証されています）。次に、最初と最後の文字が同じであることは既にわかっているため、2 番目の文字から最後の 2 番目の文字まで、部分文字列全体をチェックする必要はありません。したがって、部分文字列が「test」であり、部分文字列が同じ文字で予約されていることを常に保証している場合、実際には「test」をチェックする必要はなく、代わりに「es」をチェックするだけで済みます。これ'
スマート ソリューション:
extension Collection {
func generateOrderedPairIndexPermutations() -> [(Index,Index)] {
if count < 2 {
return []
}
var perms: [(Index,Index)] = []
var firstIndex = startIndex
while firstIndex != endIndex {
var secondIndex = index(firstIndex, offsetBy: 1)
while secondIndex != endIndex {
perms.append((firstIndex,secondIndex))
secondIndex = index(secondIndex, offsetBy: 1)
}
firstIndex = index(firstIndex, offsetBy: 1)
}
return perms
}
}
extension String {
func generateCharacterMapping() -> [Character : [Int]] {
var characterMapping: [Character : [Int]] = [:]
for (index, char) in characters.enumerated() {
if let indicesOfChar = characterMapping[char] {
characterMapping[char] = indicesOfChar + [index]
} else {
characterMapping[char] = [index]
}
}
return characterMapping
}
func containsAPalindromeSmart(ignoringWhitespace: Bool = true) -> Int {
let numChars = length
if numChars < 2 { return 0 }
let stringToCheck = (ignoringWhitespace ? self.components(separatedBy: .whitespaces).joined(separator: "") : self).lowercased()
let characterMapping = stringToCheck.generateCharacterMapping()
var count: Int = 0
var checkedChars: Set<Character> = Set()
for char in stringToCheck.characters {
if checkedChars.contains(char) == false {
if let characterIndices = characterMapping[char], characterIndices.count > 1 {
let perms = characterIndices.generateOrderedPairIndexPermutations()
for (i,j) in perms {
let startCharIndex = characterIndices[i]
let endCharIndex = characterIndices[j]
if endCharIndex - startCharIndex < 3 {
count += 1
} else {
let substring = stringToCheck.substring(with: Range(uncheckedBounds: (stringToCheck.index(stringToCheck.startIndex, offsetBy: startCharIndex+1), stringToCheck.index(stringToCheck.startIndex, offsetBy: endCharIndex))))
if substring.isPalindrome() {
count += 1
}
}
}
checkedChars.insert(char)
}
}
}
return count
}
}
私はこの解決策についてかなり気分が良かった. しかし、それが実際にどれほど速いかはわかりませんでした。本当に速かったです
XCTest を使用してパフォーマンスを測定し、いくつかのパフォーマンス テストで各アルゴリズムを実行しました。この文字列をベース ソースとして使用する: 「ここには複数の回文があります」「それは私が見た車または猫でしたか」、より厳密な入力文字列を使用するように提案に基づいて更新されました。小文字で ( " thereremultiplepalindromesinhere" "wasitacaroracatisaw" )、この文字列を 2 倍したコピーも作成しました ( "thereremultiplepalindromesinherethereremultiplepalindromesinhere" wasitacaroracatisawwasitacaroracatisaw
より正確なデータを取得するために、各テストを 10 回反復して実行しました (もっと反復したかったのですが、元のソリューションと私の Naive ソリューションの両方が 4 回以上のテストでタイムリーに終了しませんでした)。収集したタイミング データは次のとおりです (スプレッドシートのスクリーンショットは、ここに再度入力するよりも簡単でした)。
更新しました
更新され
た緑は著者です。赤はナイーブ ソリューションです。オレンジはスマートなソリューションです
ご覧のとおり、元のソリューションと私の単純なソリューションの両方が 2 次時間で動作します (あなたのソリューションは r=0.9997 の 2 次相関係数を持ち、私の単純なソリューションは r=0.9999 の係数を持ちます。つまり、非常に明確に 2 次です!)。私の単純なソリューションはあなたのソリューションの下にあるようですが、すでに知っているように、両方とも二次的に増加しているため、O(n^2) です。
私のスマート ソリューションの興味深い点は、直線的に見えることです。回帰計算機で設定した小さな 5 ポイント データの相関係数は r=0.9917 です。直線的でない場合は、非常に近いので気にしません。
現在、すべてのソリューションは二次時間で動作します。ため息。しかし、少なくともバグは発見され、対処され、今日では科学が普及しました。残念なことに、私の「スマート ソリューション」は実際には直線的ではありませんでした。ただし、入力文字列がまだ巨大な回文ではない場合 (最終的に変更したものなど)、「Smart Solution」の最適化により、2次時間ではあるものの、はるかに高速に実行されることに注意してください。 .
私のアルゴリズムが Manacher のアルゴリズムより理解しやすいかどうかはわかりませんが、うまく説明できれば幸いです。結果はかなり有望なので、うまく活用していただければ幸いです。これは実際にはまだ真実です。有望なアルゴリズムだと思います。おそらく私のコードgenerateOrderedPairIndexPermutationsは最高ではありません。
kraskevich によって発見されたバグに対処するために更新されました