在惯用的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 "

它有一种具有非常优雅的功能解决方案的感觉,但我看不出方法的最佳起点.

Answer 1

只是想补充一点,基金会实际上有一种方法(自iOS 8/macOS 10.10起),它完全是这样做的:

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

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

虽然这对找到惯用/功能实现方法没有帮助,但它可能会帮助那些只需要完成工作的人.:)

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

现在"解除"方法到序列类型:

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

现在可以将"公共前缀"功能定义为

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

字符串也是(再次)它们的字符集合. (从17.05.2017开始使用Swift 4.0快照测试.)