回文数 swift 优化
palindromes count swift optimization
嘿，我有一个关于优化回文计数算法的问题
Task: Find count of palindromes in string.
在我的函数中，我使用 "in the forehead" 方法，它类似于 O(n^2)
你们能帮忙在 O(n) 或 O(nlogn)
中完成吗
func isPalindrome(string: String) -> Bool {
let str = (string.lowercased())
let strWithoutSpace = str.components(separatedBy: .whitespaces).joined(separator: "")
let strArray = Array(strWithoutSpace.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
}
func palindromsInString(string: String) -> Int {
var arrayOfChars = Array(string.characters)
var count = 0
for i in 0..<arrayOfChars.count-1 {
for x in i+1..<arrayOfChars.count {
if isPalindrome(string: String(arrayOfChars[i...x])) {
count+=1
}
}
}
return count
}
是的，在我的例子中，一个字母不能是回文
你可以用Manacher的算法在线性时间内求解。该算法通常用于查找最长回文，但它计算的是字符串中每个位置的中心位于特定位置的回文的最大长度。
您可以在this question中找到该算法的描述和实现。
我不熟悉 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 解决方案后，它看起来像一个标准的蛮力解决方案，但简单易读。
我对不同算法的第一个想法也是相当蛮力，但这是一种完全不同的方法，所以我称之为朴素解决方案。
Naive 解决方案的想法是创建原始字符串的子字符串数组，并检查每个子字符串是否为回文。我确定子字符串的方法是从可能的最大子字符串（原始字符串）开始，然后获取长度为 string.length-1 的 2 个子字符串，然后是 string.length-2 等等，直到最后我得到所有子字符串长度为 2（我忽略了长度为 1 的子字符串，因为你说长度为 1 的字符串不能是回文）。
ie: substrings of "test" greater than length 1 would be:
["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
}
}
我很清楚这个算法会很慢，但我想将它实现为我的实际解决方案的第二个基线。
我将此解决方案称为智能解决方案。它是一种多通道解决方案，利用了字符串中字符的数量和位置。
在第一遍中，我生成了所谓的字符映射。字符映射是一个将 Character 映射到索引数组的字典。因此，您遍历字符串并将每个字符的索引添加到存储在其字符值下的数组中作为键。
这个想法是回文只能存在于由相同字母结尾的字符串中。因此，您只需检查字符串中特定字母索引处的子字符串。在单词 "tattoo" 中，您有 3 个不同的字母："t"、"a"、"o"。字符映射如下所示：
t: [0,2,3]
a: [1]
o: [4,5]
我现在知道回文只能存在于(0,2), (2,3), (4,5)之间的这个词中。所以我只需要检查3个子串(0,2), (0,3), (2,3), and (4, 5).所以我只需要检查4个子字符串。就是这个主意。一旦您检查了所有可能的以特定字母结尾的子字符串，您就可以忽略遇到的以该字母开头的任何其他子字符串，因为您已经检查过它们。
在第二遍中，我检查字符串中的每个字符，如果我还没有检查那个字母，我检查由 generateOrderedPairIndexPermutations 生成的 排列索引对字符映射中的 索引并检查子字符串以查看它们是否为回文。然后我在这里做2个优化。首先，如果起始字符索引和结束字符索引之间的距离小于 3，则它一定是回文（距离为 1 表示它们是连续的，距离为 2 表示它们之间只有一个字母，因此也gua运行teed 是一个回文）。其次，因为我已经知道第一个字符和最后一个字符是相同的，所以我不需要检查整个子字符串，只需从第二个字母到倒数第二个字母。因此，如果子字符串是 "test"，并且我总是 gua运行 认为子字符串由同一个字母结尾，我实际上不需要检查 "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来衡量性能，我运行每个算法都通过了一些性能测试。使用此字符串作为基本来源："There are multiple palindromes in here""Was it a car or a cat I saw"，根据建议更新以使用更严格的输入字符串 ，这是 3319 个字符长，当空格被删除并小写时（"therearemultiplepalindromesinhere""wasitacaroracatisaw"), 我还创建了这个字符串乘以 2 的副本 ("therearemultiplepalindromesinheretherearemultiplepalindromesinhere"wasitacaroracatisawwasitacaroracatisaw )、4 次、8 次和 10 次。由于我们试图确定算法的 O()，因此按比例增加字母数量并测量比例因子是可行的方法。
为了获得更准确的数据，我 运行 每次测试都进行了 10 次迭代（我希望有更多的迭代，但是原始解决方案和我的 Naive 解决方案都没有及时完成在上面的测试中 4)。这是我收集的时间数据（电子表格的屏幕截图比在此处再次输入更容易）：
已更新
已更新
绿色是作者；红色是朴素的解决方案； O运行ge 是智能解决方案
如您所见，您的原始解决方案和我的 Naive Solution 均以二次时间运行（您的解决方案的二次相关系数为 r=0.9997，而我的 Naive Solution 的系数为 r= 0.9999；所以，非常明显的二次方！）。我的 Naive 解决方案似乎在您的解决方案之下，但它们都以二次方式增加，因此正如我们已经知道的那样，它们是 O(n^2)。
我的智能解决方案的有趣之处在于它看起来是线性的！我的小型 5 点数据集通过回归计算器得到，相关系数为 r=0.9917！因此，如果它不是线性的，那么它非常接近，我不会在意。
现在所有的解决方案都以二次时间运行。 乐叹。但至少 bug 被发现、解决了，并且科学在今天占了上风。真可惜我的 "Smart Solution" 实际上并不是线性的。但是，我会注意到，如果输入字符串还不是一个巨大的回文（就像我最终将其更改为的那样），那么 "Smart Solution" 的优化会使其执行得更快，尽管仍然是二次回文时间.
我不知道我的算法是否比Manacher的算法更容易理解，但我希望我解释得很好。结果非常有希望，所以我希望你能从中找到一个好的用途。 这话其实还是对的。我认为这是一个很有前途的算法。也许我的 generateOrderedPairIndexPermutations 代码不是最好的。
已更新以解决 kraskevich 发现的错误
这是一个 "functional programming" 解决方案，它受过程的指数性质的影响比接受的答案小得多。 （也少了很多代码）
它在短 (19) 字符串上快 80%，在长字符串 (190) 上快 90 倍。我还没有正式证明它，但它似乎是线性的 O(n)?.
public func countPalindromes(in text:String) -> Int
{
let words = text.lowercased()
.components(separatedBy:CharacterSet.letters.inverted)
.filter{![=10=].isEmpty}
.joined(separator:"")
let sdrow = String(words.characters.reversed())
let splits = zip( sdrow.characters.indices.dropFirst().reversed(),
words.characters.indices.dropFirst()
)
.map{ (sdrow.substring(from:[=10=]),words.substring(from:), words[...] ) }
let count = splits.map{[=10=].1.commonPrefix(with:[=10=].0)} // even
.filter{ ![=10=].isEmpty }
.reduce(0){[=10=] + .characters.count}
+ splits.map{ .commonPrefix(with: + [=10=])} // odd
.filter{[=10=].characters.count > 1 }
.reduce(0){[=10=] + .characters.count - 1}
return count
}
// how it works ...
// words contains the stripped down text (with only letters)
//
// sdrow is a reversed version of words
//
// splits creates split pairs for each character in the string.
// Each tuple in the array contains a reversed left part, a right part
// and the splitting character
// The right part includes the splitting character
// but the left part does not.
//
// [(String,String,String)] for [(left, right, splitChar)]
//
// The sdrow string produces the left part in reversed letter order .
// This "mirrored" left part will have a common prefix with the
// right part if the split character's position is in the middle (+1)
// of a palindrome that has an even number of characters
//
// For palindromes with an odd number of characters,
// the reversed left part needs to add the splitting character
// to match its common prefix with the right part.
//
// count computes the total of odd and even palindromes from the
// size of common prefixes. Each of the common prefix can produce
// as many palindromes as its length (minus one for the odd ones)
[编辑]我还制作了一个过程版本用于比较目的，因为我知道编译器可以比声明式代码更好地优化过程代码。
它是 Array 类型的扩展（因此它可以计算任何可比较的回文）。
extension Array where Element:Comparable
{
public func countPalindromes() -> Int
{
if count < 2 { return 0 }
var result = 0
for splitIndex in (1..<count)
{
var leftIndex = splitIndex - 1
var rightIndex = splitIndex
var oddPalindrome = true
var evenPalindrome = true
while leftIndex >= 0 && rightIndex < count
{
if evenPalindrome
&& self[leftIndex] == self[rightIndex]
{ result += 1 }
else
{ evenPalindrome = false }
if oddPalindrome
&& rightIndex < count - 1
&& self[leftIndex] == self[rightIndex+1]
{ result += 1 }
else
{ oddPalindrome = false }
guard oddPalindrome || evenPalindrome
else { break }
leftIndex -= 1
rightIndex += 1
}
}
return result
}
}
public func countPalindromesFromArray(in text:String) -> Int
{
let words = text.lowercased()
.components(separatedBy:CharacterSet.letters.inverted)
.filter{![=11=].isEmpty}
.joined(separator:"")
return Array(words.characters).countPalindromes()
}
它的执行速度比声明式快 5 到 13 倍，比公认答案快 1200 倍。
声明式解决方案的性能差异越来越大，这告诉我它不是 O(n)。程序版本可能是 O(n)，因为它的时间会随着回文的数量而变化，但会与数组的大小成正比。
嘿，我有一个关于优化回文计数算法的问题
Task: Find count of palindromes in string.
在我的函数中，我使用 "in the forehead" 方法，它类似于 O(n^2) 你们能帮忙在 O(n) 或 O(nlogn)
中完成吗func isPalindrome(string: String) -> Bool {
let str = (string.lowercased())
let strWithoutSpace = str.components(separatedBy: .whitespaces).joined(separator: "")
let strArray = Array(strWithoutSpace.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
}
func palindromsInString(string: String) -> Int {
var arrayOfChars = Array(string.characters)
var count = 0
for i in 0..<arrayOfChars.count-1 {
for x in i+1..<arrayOfChars.count {
if isPalindrome(string: String(arrayOfChars[i...x])) {
count+=1
}
}
}
return count
}
是的，在我的例子中，一个字母不能是回文
你可以用Manacher的算法在线性时间内求解。该算法通常用于查找最长回文，但它计算的是字符串中每个位置的中心位于特定位置的回文的最大长度。
您可以在this question中找到该算法的描述和实现。
我不熟悉 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 解决方案后，它看起来像一个标准的蛮力解决方案，但简单易读。
我对不同算法的第一个想法也是相当蛮力，但这是一种完全不同的方法，所以我称之为朴素解决方案。
Naive 解决方案的想法是创建原始字符串的子字符串数组，并检查每个子字符串是否为回文。我确定子字符串的方法是从可能的最大子字符串（原始字符串）开始，然后获取长度为 string.length-1 的 2 个子字符串，然后是 string.length-2 等等，直到最后我得到所有子字符串长度为 2（我忽略了长度为 1 的子字符串，因为你说长度为 1 的字符串不能是回文）。
ie: substrings of "test" greater than length 1 would be:
["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
}
}
我很清楚这个算法会很慢，但我想将它实现为我的实际解决方案的第二个基线。
我将此解决方案称为智能解决方案。它是一种多通道解决方案，利用了字符串中字符的数量和位置。
在第一遍中，我生成了所谓的字符映射。字符映射是一个将 Character 映射到索引数组的字典。因此，您遍历字符串并将每个字符的索引添加到存储在其字符值下的数组中作为键。
这个想法是回文只能存在于由相同字母结尾的字符串中。因此，您只需检查字符串中特定字母索引处的子字符串。在单词 "tattoo" 中，您有 3 个不同的字母："t"、"a"、"o"。字符映射如下所示：
t: [0,2,3]
a: [1]
o: [4,5]
我现在知道回文只能存在于(0,2), (2,3), (4,5)之间的这个词中。所以我只需要检查3个子串(0,2), (0,3), (2,3), and (4, 5).所以我只需要检查4个子字符串。就是这个主意。一旦您检查了所有可能的以特定字母结尾的子字符串，您就可以忽略遇到的以该字母开头的任何其他子字符串，因为您已经检查过它们。
在第二遍中，我检查字符串中的每个字符，如果我还没有检查那个字母，我检查由 generateOrderedPairIndexPermutations 生成的 排列索引对字符映射中的 索引并检查子字符串以查看它们是否为回文。然后我在这里做2个优化。首先，如果起始字符索引和结束字符索引之间的距离小于 3，则它一定是回文（距离为 1 表示它们是连续的，距离为 2 表示它们之间只有一个字母，因此也gua运行teed 是一个回文）。其次，因为我已经知道第一个字符和最后一个字符是相同的，所以我不需要检查整个子字符串，只需从第二个字母到倒数第二个字母。因此，如果子字符串是 "test"，并且我总是 gua运行 认为子字符串由同一个字母结尾，我实际上不需要检查 "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来衡量性能，我运行每个算法都通过了一些性能测试。使用此字符串作为基本来源："There are multiple palindromes in here""Was it a car or a cat I saw"，根据建议更新以使用更严格的输入字符串 ，这是 3319 个字符长，当空格被删除并小写时（"therearemultiplepalindromesinhere""wasitacaroracatisaw"), 我还创建了这个字符串乘以 2 的副本 ("therearemultiplepalindromesinheretherearemultiplepalindromesinhere"wasitacaroracatisawwasitacaroracatisaw )、4 次、8 次和 10 次。由于我们试图确定算法的 O()，因此按比例增加字母数量并测量比例因子是可行的方法。
为了获得更准确的数据，我 运行 每次测试都进行了 10 次迭代（我希望有更多的迭代，但是原始解决方案和我的 Naive 解决方案都没有及时完成在上面的测试中 4)。这是我收集的时间数据（电子表格的屏幕截图比在此处再次输入更容易）：
已更新
已更新
绿色是作者；红色是朴素的解决方案； O运行ge 是智能解决方案
如您所见，您的原始解决方案和我的 Naive Solution 均以二次时间运行（您的解决方案的二次相关系数为 r=0.9997，而我的 Naive Solution 的系数为 r= 0.9999；所以，非常明显的二次方！）。我的 Naive 解决方案似乎在您的解决方案之下，但它们都以二次方式增加，因此正如我们已经知道的那样，它们是 O(n^2)。
我的智能解决方案的有趣之处在于它看起来是线性的！我的小型 5 点数据集通过回归计算器得到，相关系数为 r=0.9917！因此，如果它不是线性的，那么它非常接近，我不会在意。
现在所有的解决方案都以二次时间运行。 乐叹。但至少 bug 被发现、解决了，并且科学在今天占了上风。真可惜我的 "Smart Solution" 实际上并不是线性的。但是，我会注意到，如果输入字符串还不是一个巨大的回文（就像我最终将其更改为的那样），那么 "Smart Solution" 的优化会使其执行得更快，尽管仍然是二次回文时间.
我不知道我的算法是否比Manacher的算法更容易理解，但我希望我解释得很好。结果非常有希望，所以我希望你能从中找到一个好的用途。 这话其实还是对的。我认为这是一个很有前途的算法。也许我的 generateOrderedPairIndexPermutations 代码不是最好的。
已更新以解决 kraskevich 发现的错误
这是一个 "functional programming" 解决方案，它受过程的指数性质的影响比接受的答案小得多。 （也少了很多代码）
它在短 (19) 字符串上快 80%，在长字符串 (190) 上快 90 倍。我还没有正式证明它，但它似乎是线性的 O(n)?.
public func countPalindromes(in text:String) -> Int
{
let words = text.lowercased()
.components(separatedBy:CharacterSet.letters.inverted)
.filter{![=10=].isEmpty}
.joined(separator:"")
let sdrow = String(words.characters.reversed())
let splits = zip( sdrow.characters.indices.dropFirst().reversed(),
words.characters.indices.dropFirst()
)
.map{ (sdrow.substring(from:[=10=]),words.substring(from:), words[...] ) }
let count = splits.map{[=10=].1.commonPrefix(with:[=10=].0)} // even
.filter{ ![=10=].isEmpty }
.reduce(0){[=10=] + .characters.count}
+ splits.map{ .commonPrefix(with: + [=10=])} // odd
.filter{[=10=].characters.count > 1 }
.reduce(0){[=10=] + .characters.count - 1}
return count
}
// how it works ...
// words contains the stripped down text (with only letters)
//
// sdrow is a reversed version of words
//
// splits creates split pairs for each character in the string.
// Each tuple in the array contains a reversed left part, a right part
// and the splitting character
// The right part includes the splitting character
// but the left part does not.
//
// [(String,String,String)] for [(left, right, splitChar)]
//
// The sdrow string produces the left part in reversed letter order .
// This "mirrored" left part will have a common prefix with the
// right part if the split character's position is in the middle (+1)
// of a palindrome that has an even number of characters
//
// For palindromes with an odd number of characters,
// the reversed left part needs to add the splitting character
// to match its common prefix with the right part.
//
// count computes the total of odd and even palindromes from the
// size of common prefixes. Each of the common prefix can produce
// as many palindromes as its length (minus one for the odd ones)
[编辑]我还制作了一个过程版本用于比较目的，因为我知道编译器可以比声明式代码更好地优化过程代码。
它是 Array 类型的扩展（因此它可以计算任何可比较的回文）。
extension Array where Element:Comparable
{
public func countPalindromes() -> Int
{
if count < 2 { return 0 }
var result = 0
for splitIndex in (1..<count)
{
var leftIndex = splitIndex - 1
var rightIndex = splitIndex
var oddPalindrome = true
var evenPalindrome = true
while leftIndex >= 0 && rightIndex < count
{
if evenPalindrome
&& self[leftIndex] == self[rightIndex]
{ result += 1 }
else
{ evenPalindrome = false }
if oddPalindrome
&& rightIndex < count - 1
&& self[leftIndex] == self[rightIndex+1]
{ result += 1 }
else
{ oddPalindrome = false }
guard oddPalindrome || evenPalindrome
else { break }
leftIndex -= 1
rightIndex += 1
}
}
return result
}
}
public func countPalindromesFromArray(in text:String) -> Int
{
let words = text.lowercased()
.components(separatedBy:CharacterSet.letters.inverted)
.filter{![=11=].isEmpty}
.joined(separator:"")
return Array(words.characters).countPalindromes()
}
它的执行速度比声明式快 5 到 13 倍，比公认答案快 1200 倍。
声明式解决方案的性能差异越来越大，这告诉我它不是 O(n)。程序版本可能是 O(n)，因为它的时间会随着回文的数量而变化，但会与数组的大小成正比。