Andrew Ebling Andrew Ebling - 18 days ago 9
Swift Question

Find the common prefix of two strings in idiomatic Swift

Other than the brute force approach of iterating over string characters and comparing them, what is the most idiomatic approach to finding the longest common prefix of two Strings in Swift?

For example, the implementation of

commonPrefixWith()
in this snippet:

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 "


It has that kind of feel about it of something which has a really elegant functional solution, but I cannot see the best starting point for an approach.

Answer

Here is another possible "functional" approach. As a tool, we need a method to "truncate" a sequence according to a predicate. The following uses ideas from https://github.com/oisdk/SwiftSequence/blob/master/SwiftSequence/TakeDrop.swift.

First define takeWhile for a generator type:

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

Now "lift" the method to sequence types:

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

This can be used quite generally, here is a simple example:

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

The "common prefix" function can now be defined as

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

Example:

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

Explanation:

zip(self.characters, other.characters) enumerates both character sequences in parallel and creates a (lazy evaluated) sequence of pairs:

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

.takeWhile({$0 == $1}) limits this sequence to the initial part of identical characters in both strings:

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

.map({ $1 }) maps each tuple to the second element, returning the array

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

Finally, String(...) combines the characters to a string.

Comments