草庐IT

关于算法：回文数快速优化

codeneng 2023-03-28 原文

palindromes count swift optimization

嘿，我有一个关于优化回文计数算法的问题

Task: Find count of palindromes in string.

在我的函数中，我使用"额头"方法，就像 O(n^2)
你们能帮我在 O(n) 或 O(nlogn)

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
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
}

是的，在我的例子中，一个字母不能是回文

  • 可能属于 Code Review 交易所？
  • @matt 好的，我尝试在那里发帖
  • 我不认为像在字符串中找到回文的"计数"这样的任务是 O(n) 的任务。
  • @Redu 和原作者，请参阅我的答案，了解我认为是 O(n) 解决方案或接近 O(n) 的解决方案。

我不熟悉 Manacher 的算法，但我一直很喜欢找出有效的算法，所以我想我会尝试一下。

你确定一个字符串是否是回文的算法看起来像我想出的那种，所以我决定只使用你的 isPalindrome 函数，虽然我把它改成了 String 相反，我删除了空格删除逻辑，因为我觉得需要在调用调用中而不是在回文确定函数本身中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 解决方案。

Naive 解决方案的想法是创建原始字符串的子字符串数组，并检查每个子字符串是否为回文。我确定子字符串的方法是从可能的最大子字符串(原始字符串)开始，然后得到 2 个长度为 string.length-1 的子字符串，然后是 string.length-2，依此类推，直到最后我得到所有长度为 2 的子字符串(我忽略了长度为 1 的子字符串，因为你说长度为 1 的字符串不能是回文)。

ie: substrings of"test" greater than length 1 would be:

["test"]
["tes","est"]
["te","es","st"]

所以你只需遍历每个数组并检查是否有回文，如果是则增加计数：

天真的解决方案：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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"。字符映射如下所示：

1
2
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 个子字符串。就是这个想法。一旦您检查了所有可能以特定字母结尾的子字符串，您就可以忽略遇到的以该字母开头的任何其他子字符串，因为您已经检查过它们。

在第二遍中，我检查字符串中的每个字符，如果我还没有检查过那个字母，我检查由 generateOrderedPairIndexPermutations 为字符映射中的索引生成的排列索引对并检查子串，看看它们是否是回文。然后我在这里做了 2 次优化。首先，如果起始字符索引和结束字符索引之间的距离小于3，则它必须是回文(距离1表示它们是连续的，距离2表示它们之间有一个字母，因此也保证是回文)。其次，因为我已经知道第一个和最后一个字符是相同的，所以我不需要检查整个子字符串，只需从第二个字母到倒数第二个字母。因此，如果子字符串是 "test"，并且我总是保证子字符串以同一个字母结尾，我实际上不需要检查 "test"，而是可以检查"es"。这是一个较小的优化，但仍然是一个不错的优化。

智能解决方案：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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 ("therearemultiplepalindromesinheretherarearemultiplepalindromesinhere"wasitacaroracatisawwasitacaroracatisaw)、乘以 4、乘以 8 和乘以 10。由于我们试图确定算法的 O()，因此将字母的数量向上缩放并且测量比例因子是要走的路。

为了获得更准确的数据，我对每个测试进行了 10 次迭代(我本来希望更多次迭代，但是原始解决方案和我的 Naive 解决方案都没有及时完成上述测试次 4)。这是我收集的计时数据(电子表格的屏幕截图比在此处再次输入更容易)：

已更新

已更新
绿色是作者；红色是朴素的解决方案；橙色是智能解决方案

如您所见，您的原始解决方案和我的朴素解决方案都在二次时间中运行(您的解决方案的二次相关系数为 r=0.9997，而我的朴素解决方案的系数为 r=0.9999；所以，很明显是二次的！)。我的 Naive 解决方案似乎在您的解决方案之下，但它们都是二次增长的，因此我们已经知道是 O(n^2)。

我的智能解决方案的有趣之处在于它看起来是线性的！我通过回归计算器设置的 5 点小数据集，其相关系数为 r=0.9917！因此，如果它不是线性的，那么它是如此接近以至于我不会在意。

现在所有的解决方案都在二次时间中运行。乐叹息。但至少这个错误被发现，解决了，科学在今天占了上风。令人遗憾的是，我的"智能解决方案"实际上并没有以线性方式结束。但是，我会注意到，如果输入字符串还不是一个巨大的回文串(就像我最终将其更改为的那样)，那么"智能解决方案"的优化使其执行得更快，尽管仍然是二次方时间。

我不知道我的算法是否比 Manacher 的算法更容易理解，但我希望我能解释清楚。结果非常有希望，所以我希望你能从中找到一个很好的用途。这实际上仍然是正确的。我认为这是一个很有前途的算法。也许我的 generateOrderedPairIndexPermutations 代码不是最好的。

更新以解决 kraskevich 发现的错误

  • 您的智能解决方案似乎通过查找表实现了相当不错的优化，并且一旦它也处理了空白，它确实是一个可行的解决方案，但我仍然不认为它可以是 O(n)，因为工作量它肯定会根据输入字符串而改变。例如，它有一个很长的回文，比如"我看到的是汽车还是猫"，在一个很长的句子中，我想它还有很多事情要做。它可能是像 O(xn) 这样的线性时间复杂度，但我想不是 O(n)。不过还是很聪明的。
  • 对于包含多个重复相同字母的字符串，此解决方案返回什么？如果我做对了，它会为字符串"aaa"返回 2，但它应该是 3。
  • @kraskevich 在任务"是的，在我的例子中，一个字母不能是回文"
  • 我知道不是。 aa,aa,aaa 都是回文。如果这个解决方案计算了所有不同的回文，那么它也不正确(例如，尝试 "aabcaa" 测试用例)。
  • @kraskevich 你是绝对正确的。有一个错误。我应该检查所有对，而不是只检查连续的索引对。我今天会调整一下，并更新答案。我无法想象它会减慢太多。

您可以使用 Manacher 算法在线性时间内求解。该算法通常用于查找最长回文，但它计算回文的最大长度，该回文的中心在字符串中每个位置的特定位置。

你可以在这个问题中找到这个算法的描述和实现。

  • 嘿，感谢您的回答，我尝试使用 Manacher 的算法解决此问题。我有很多问题。也许有一些算法更容易理解开始再次感谢；)
  • @DmitrievichR 我不知道有任何比 O(n ^ 2) 更快的非常简单的算法来解决这个问题。
  • @kraskevich 和原作者，请参阅我的答案，了解我认为是 O(n) 解决方案或接近 O(n) 的解决方案。

这是一个"函数式编程"解决方案，与公认的答案相比，它受过程指数性质的影响要小得多。 (代码也少了很多)

在短弦 (19) 上快 80%，在长弦 (190) 上快 90 倍。我还没有正式证明它，但它似乎是线性 O(n)?.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public func countPalindromes(in text:String) -> Int
{
   let words  = text.lowercased()
                    .components(separatedBy:CharacterSet.letters.inverted)
                    .filter{!$0.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:$0),words.substring(from:$1), words[$1...$1] ) }

   let count  = splits.map{$0.1.commonPrefix(with:$0.0)}  // even
                      .filter{ !$0.isEmpty }
                      .reduce(0){$0 + $1.characters.count}
              + splits.map{ $1.commonPrefix(with:$2 + $0)} // odd
                      .filter{$0.characters.count > 1 }
                      .reduce(0){$0 + $1.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)

[EDIT] 我还制作了一个程序版本以进行比较，因为我知道编译器可以比其声明性对应物更好地优化程序代码。

它是 Array 类型的扩展(因此它可以计算任何类似的回文数)。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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{!$0.isEmpty}
                    .joined(separator:"")
   return Array(words.characters).countPalindromes()
}

它的执行速度比声明式的快 5 到 13 倍，比接受的答案快 1200 倍。

声明式解决方案的性能差异越来越大，这告诉我这不是 O(n)。程序版本可能是 O(n)，因为它的时间会随着回文数的数量而变化，但与数组的大小成正比。

回文关于nbspbrsectionalgorithmstring-algorithmswift

有关关于算法：回文数快速优化的更多相关文章

  1. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  2. ruby-on-rails - 关于 Ruby 的一般问题 - 2

    我在我的rails应用程序中安装了来自github.com的acts_as_versioned插件，但有一段代码我不完全理解，我希望有人能帮我解决这个问题class_eval我知道block内的方法(或任何它是什么)被定义为类内的实例方法，但我在插件的任何地方都找不到定义为常量的CLASS_METHODS，而且我也不确定是什么here，并且有问题的代码从lib/acts_as_versioned.rb的第199行开始。如果有人愿意告诉我这里的内幕，我将不胜感激。谢谢-C 最佳答案 这是一个异端。http://en.wikipedia

  3. ruby - 如何以表格格式快速打印 Ruby 哈希值？ - 2

    有没有办法快速将表格格式的ruby​​哈希打印到文件中？如:keyAkeyBkeyC...1232343451253474456...其中散列的值是不同大小的数组。还是使用双循环是唯一的方法？谢谢 最佳答案 试试我写的这个gem(在表中打印散列、ruby对象、ActiveRecord对象):http://github.com/arches/table_print 关于ruby-如何以表格格式快速打印Ruby哈希值？，我们在StackOverflow上找到一个类似的问题：

  4. ruby - 我怎样才能更好地了解/了解更多关于 Ruby 的知识？ - 2

    按照目前的情况，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visitthehelpcenter指导。关闭9年前。我最近开始学习Ruby，这是我的第一门编程语言。我对语法感到满意，并且我已经完成了许多只教授相同基础知识的教程。我已经写了一些小程序(包括我自己的数组排序方法，在有人告诉我谷歌“冒泡排序”之前我认为它非常聪明)，但我觉得我需要尝试更大更难的东西来理解更多关于Ruby.关于如何执行此操作的任何想法？

  5. ruby - 关于 Ruby 中 Dir[] 和 File.join() 的混淆 - 2

    我在Ruby中遇到了一个关于Dir[]和File.join()的简单程序，blobs_dir='/path/to/dir'Dir[File.join(blobs_dir,"**","*")].eachdo|file|FileUtils.rm_rf(file)ifFile.symlink?(file)我有两个困惑:首先，File.join(@blobs_dir,"**","*")中的第二个和第三个参数是什么意思？其次，Dir[]在Ruby中有什么用？我只知道它等价于Dir.glob()，但是，我对Dir.glob()确实不是很清楚。 最佳答案

  6. 电脑启动后显示器黑屏怎么办？排查下面4个问题，快速解决 - 2

    电脑启动出现显示器黑屏是一个相当常见的问题。如果您遇到了这个问题，不要惊慌，因为它有很多可能的原因，可以采取一些简单的措施来解决它。在本文中，小编将介绍下面4种常见的电脑启动后显示器黑屏的原因，排查这些原因，快速解决！ 演示机型：联想Ideapad700-15ISK-ISE系统版本：Windows10一、显示器问题如果出现电脑启动后显示器黑屏的情况。那么首先您需要检查一下显示器是否正常工作。您可以通过更换另一个显示器或将当前显示器连接到另一台计算机来检查显示器是否存在问题。如果问题仍然存在，那么您可以排除显示器故障的可能性。 二、显卡问题如果您的电脑配备了独立显卡，那么显卡故障也可能是导致电脑

  7. 100个python算法超详细讲解：画直线 - 2

    1．问题描述使用Python的turtle（海龟绘图）模块提供的函数绘制直线。2．问题分析一幅复杂的图形通常都可以由点、直线、三角形、矩形、平行四边形、圆、椭圆和圆弧等基本图形组成。其中的三角形、矩形、平行四边形又可以由直线组成，而直线又是由两个点确定的。我们使用Python的turtle模块所提供的函数来绘制直线。在使用之前我们先介绍一下turtle模块的相关知识点。turtle模块提供面向对象和面向过程两种形式的海龟绘图基本组件。面向对象的接口类如下：1）TurtleScreen类：定义图形窗口作为绘图海龟的运动场。它的构造器需要一个tkinter.Canvas或ScrolledCanva

  8. elasticsearch源码关于TransportSearchAction【阶段三】 - 2

    1.回顾.TransportServicepublicclassTransportServiceextendsAbstractLifecycleComponentTransportService：方法：1publicfinalTextendsTransportResponse>voidsendRequest(finalTransport.Connectionconnection,finalStringaction,finalTransportRequestrequest,finalTransportRequestOptionsoptions,TransportResponseHandlerT>

  9. 关于Qt程序打包后运行库依赖的常见问题分析及解决方法 - 2

    目录一.大致如下常见问题：（1）找不到程序所依赖的Qt库version`Qt_5'notfound(requiredby（2）CouldnotLoadtheQtplatformplugin"xcb"in""eventhoughitwasfound（3）打包到在不同的linux系统下，或者打包到高版本的相同系统下，运行程序时，直接提示段错误即segmentationfault，或者Illegalinstruction(coredumped)非法指令（4）ldd应用程序或者库，查看运行所依赖的库时，直接报段错误二.问题逐个分析，得出解决方法：（1）找不到程序所依赖的Qt库version`Qt_5'

  10. ruby - 对回文产品问题感到困惑 - 2

    我一直在学习Ruby，所以我想我应该尝试一下项目中的一些Euler难题。尴尬的是，我只完成了问题4...问题4如下:Apalindromicnumberreadsthesamebothways.Thelargestpalindromemadefromtheproductoftwo2-digitnumbersis9009=91×99.Findthelargestpalindromemadefromtheproductoftwo3-digitnumbers.所以我想我会在嵌套的for循环中从999循环到100并测试回文，然后在找到第一个(应该是最大的)时跳出循环:final=nilrang

随机推荐