在 Swift 中寻找两个字符串的公共前缀

Question

除了遍历字符串字符并比较它们的蛮力方法之外，在Swift中找到两个字符串的最长公共前缀的最惯用方法是什么？

例如，此代码段中commonPrefixWith()的实现： let firstString = "The quick brown fox jumps over the lazy dog" let secondString = "The quick brown fox has a pogo stick" let result = firstString.commonPrefixWith(secondString) // result == "The quick brown fox " 它有一种非常优雅的功能性解决方案的感觉，但我无法看出最佳的起点。

- Andrew Ebling

---

我认为迭代字符串字符并进行比较是最快和最优雅的解决方案。 - mixel

Answer 1

我想补充一下，实际上 Foundation（自 iOS 8/macOS 10.10 开始）中有一个方法可以确切地做到这一点：

func commonPrefix(with str: String, 
                  options mask: NSString.CompareOptions = []) -> String

请参考https://developer.apple.com/reference/foundation/nsstring/1408169-commonprefix

虽然这不能帮助找到惯用/功能实现方法，但它可能有助于那些只需完成工作的人。:)

- Daniel Rinser

Answer 2

这里是另一种可能的“功能性”方法。作为一个工具，我们需要一种根据谓词“截断”序列的方法。以下代码使用了来自https://github.com/oisdk/SwiftSequence/blob/master/SwiftSequence/TakeDrop.swift的思路。

首先，定义一个生成器类型的takeWhile：

extension GeneratorType {
    /// Returns a new generator whose `next()` function returns the elements
    /// from the given generator as long they satisfy the predicate,
    /// and then returns `nil`.
    func takeWhile(predicate : (Element) -> Bool) -> AnyGenerator<Element> {
        var gen = self
        return anyGenerator( { gen.next().flatMap( { predicate($0) ? $0 : nil }) })
    }
}

现在将"lift"方法应用到序列类型：

extension SequenceType {
    /// Returns a new sequence with all initial elements from the given sequence
    /// satisfying the predicate.
    func takeWhile(predicate : (Generator.Element) -> Bool) -> AnySequence<Generator.Element> {
        return AnySequence( { self.generate().takeWhile(predicate) })
    }
}

这可以被广泛使用，这里有一个简单的例子：

for i in [1, 4, 2, 5, 3].takeWhile( {$0 < 5} ) {
    print(i)
}
// Output: 1 4 2

“公共前缀（common prefix）”函数现在可以定义为：

extension String {
    func commonPrefixWith(other: String) -> String {
        return String(zip(self.characters, other.characters).takeWhile({$0 == $1}).map({ $1 }))
    }
}

例子：

let firstString = "abc1xy"
let secondString = "abc2x"
let common = firstString.commonPrefixWith(secondString)
print(common) // abc

解释： zip(self.characters, other.characters)同时枚举两个字符序列，并创建一个（惰性评估的）对序列。

("a", "a"), ("b", "b"), ("c", "c"), ("1", "2"), ("x", "x")

.takeWhile({$0 == $1}) 限制了该序列仅包含两个字符串中相同字符的初始部分：

("a", "a"), ("b", "b"), ("c", "c")

.map({ $1 })将每个元组映射到第二个元素，并返回数组

[ "a", "b", "c"]

最后，String(...)将字符组合成字符串。

---

从 Swift 4 开始，序列有一个 prefix(while:) 方法，它接受一个布尔谓词，在这里可以使用它来代替定义自定义的 takeWhile 方法：

extension String {
    func commonPrefix(with other: String) -> String {
        return String(zip(self, other).prefix(while: { $0.0 == $0.1 }).map { $0.0 })
    }
}

字符串是由它们的字符组成的集合。

（使用2017年5月17日的Swift 4.0快照进行测试。）

- Martin R

---

感谢马丁(Martin)选择这个被采纳的答案，因为它既清晰又解释得很好。我从你的回答中学到了很多东西，不仅仅是完成工作。 - Andrew Ebling

感谢您提供了Swift 4的答案，即使没有Swift 4标签可用 :) - LC 웃

Answer 3

我尽可能地采用函数化的思维方式 :-]

正确版本

extension String {
    func commonPrefixWith(another: String) -> String {
        let a = Array(self.characters)
        let b = Array(another.characters)
        return String(
            a.enumerate()
                .filter { b.count > $0.index && b[0...$0.index] == a[0...$0.index] }
                .map { $0.1 }
        )
    }
}

错误版本

extension String {
    func commonPrefixWith(another: String) -> String {
        let b = Array(another.characters)
        return String(
            Array(self.characters)
            .enumerate()
            .filter { b.count > $0.index && b[$0.index] == $0.element }
            .map { $0.1 }
        )
    }
}

- Luca Angeletti

---

"a1b".commonPrefixWith("a2b") 返回的是 "ab" 而不是 "a" :) - Martin R

@MartinR：好的，我更新了我的代码。现在它应该是正确的，但从计算复杂度的角度来看并不是很好。 - Luca Angeletti

酷 - 谢谢！我对这个工作方式感到同样印象深刻又困惑。我认为我已经理解了filter()，但是不理解map()。请问你能解释一下吗？我熟悉$0，$1等等，但是不理解$0.1的符号表示法，而且很难查找相关信息。 - Andrew Ebling

啊 - $0.1 是访问元组中的元素。我现在明白了。 - Andrew Ebling

你能把它转换成Swift 4吗？ - Bartłomiej Semańczyk

Answer 4

这是一个使用字符的简单数组操作的递归函数解决方案。我认为这就是你要找的一行代码。

extension String {
   func sharedPrefix(with other: String) -> String {
      return characters.isEmpty || other.characters.isEmpty ? "" : (characters.first! != other.characters.first! ? "" : "\(characters.first!)" + String(Array(characters.dropFirst())).sharedPrefix(with: String(Array(other.characters.dropFirst()))))
   }
}

编辑（由原帖作者编辑）可以进一步简化为以下内容，以提高可读性，尽管这不再是一个真正的一行代码：

extension String {
    func sharedPrefix(with other: String) -> String {
        return (self.isEmpty || other.isEmpty || self.first! != other.first!) ? "" :
            "\(self.first!)" + String(Array(self.dropFirst())).sharedPrefix(with: String(Array(other.dropFirst())))
    }
}

- Joseph Bao

---

非常好的答案。为了可读性，我可能会进一步简化它，尽管现在不再是一行代码了：extension String { func sharedPrefix(with other: String) -> String { return (self.isEmpty || other.isEmpty || self.first! != other.first!) ? "" : "\(self.first!)" + String(Array(self.dropFirst())).sharedPrefix(with: String(Array(other.dropFirst()))) } } - Andrew Ebling

数组转换是不必要的，只需使用String(self.dropFirst())即可。但它仍然会创建大量中间字符串，这是低效的。 - Martin R

你不应该删除你的答案并重新发布相同内容，可以参考 https://meta.stackoverflow.com/a/251732 和 https://meta.stackoverflow.com/a/297126。 - Martin R

Answer 5

这个问题没有“优雅的功能性解决方案”。记住，你有一把锤子并不意味着每个问题都是钉子。然而，如果你想的话，可以使用Swift的高阶函数来解决这个问题：

extension String {
    func commonPrefixWith(aStr: String) -> String {
        var i = 0
        var stop = false

        return self.characters.reduce("") {
            aggregate, char in
            let index = self.startIndex.advancedBy(i)
            if !stop && index <= aStr.endIndex && char == aStr[index] {
                i++
                return aggregate + String(char)
            } else {
                stop = true
                return aggregate
            }
        }
    }
}


let firstString = "The quick brown fox jumps over the lazy dog"
let secondString = "The quick brown fox has a pogo stick"
let result = firstString.commonPrefixWith(secondString) // result == "The quick brown fox "

print("'\(result)'")

它不是完全函数式的，因为它具有副作用（i，stop），但非常接近。

- Code Different

---

感谢您的输入，Zoff。我认为被接受的答案非常优雅，并且很好地展示了如何通过将问题分解为可重用的块来以函数式的方式完成任务。 - Andrew Ebling

Answer 6

这适用于字符串、数组和其他集合。与大多数字符串操作一样，它返回一个子字符串。如果您想要一个字符串，可以使用String(result)。

extension Collection where Element: Equatable {

    func shared_prefix( with other: Self ) -> SubSequence {

        var a = dropLast(0), b = other.dropLast(0)

        while !(a.isEmpty || b.isEmpty) 
              && (a.first == b.first) {

            ( a, b ) = ( a.dropFirst(), b.dropFirst() )

        }

        return dropLast( a.count )

    }

}

使用方法：

let
    a = "It works, which is nice!",
    b = "It works and that's a fact.",
    
    result = a.shared_prefix(with:b)

print( result ) // "It works"

- original_username