How to determine longest common prefix and suffix for array of strings?

Question

Suppose I have array of strings:

["A12[1]", "A13[1]", "A14[1]"]

And I need to find the longest common prefix A1 and suffix [1].

Other examples:

["9-b", "10-b", "11-b"] -> suffix -b, no prefix

["A12", "A14", "A6"] -> prefix A, no sufix

How do I iterate over the array to find what string ends and starts every string in array?

The same string that ends every string in array is suffix. I define prefix the same way, but from the other side;) — Bartłomiej Semańczyk, Jan 25 '18 at 18:15
You could use binary search to find the longest common prefix, I'd imagine you could find the suffix the same way. Or you could use a [trie](https://en.wikipedia.org/wiki/Trie) — user3483203, Jan 25 '18 at 18:18
https://www.geeksforgeeks.org/longest-common-prefix-set-4-binary-search/ — Alexander, Jan 25 '18 at 18:20

rob mayoff · Accepted Answer · 2018-01-26T08:27:57.057

extension Collection where Element: StringProtocol {

    func longestCommonPrefix() -> String {
        guard var prefix = first.map({ String($0) }) else { return "" }
        for string in dropFirst() {
            while !string.hasPrefix(prefix) {
                prefix.removeLast()
            }
        }
        return prefix
    }

    func longestCommonSuffix() -> String {
        guard var suffix = first.map({ String($0) }) else { return "" }
        for string in dropFirst() {
            while !string.hasSuffix(suffix) {
                suffix.removeFirst()
            }
        }
        return suffix
    }

}

print(["A12[1]", "A13[1]", "A14[1]"].longestCommonPrefix()) // "A1"
print(["A12[1]", "A13[1]", "A14[1]"].longestCommonSuffix()) // "[1]"
print(["9-b", "10-b", "11-b"].longestCommonPrefix())        // ""
print(["9-b", "10-b", "11-b"].longestCommonSuffix())        // "-b"
print(["A12", "A14", "A6"].longestCommonPrefix())           // "A"
print(["A12", "A14", "A6"].longestCommonSuffix())           // ""

If you're importing Foundation, you can use its String.commonPrefix(with:) extension method to write an even shorter version:

import Foundation

extension Collection where Element: StringProtocol {
    func longestCommonPrefix() -> String {
        guard let first = self.first.map({ String($0) }) else { return "" }
        return dropFirst().reduce(first, { $0.commonPrefix(with: $1) })
    }

    func longestCommonSuffix() -> String {
        return String(self.lazy.map({ String($0.reversed()) }).longestCommonPrefix().reversed())
    }
}

I learned about commonPrefix(with:) from Martin R's answer.

That should work, but for long strings and short matching prefixes/suffixes (likely the normal case) it would be faster to write it to go from shortest matching suffix/prefix to longest. — Duncan C, Jan 26 '18 at 00:57
For the first solution without `commonPrefix` usage, consider these failing assertions: `assert(["flip Clap Glop"].longestCommonPrefix() == "", "longestCommonPrefix failed")` `assert(["Glaf Glae Glad"].longestCommonSuffix() == "", "longestCommonSuffix failed")` — Meseery, Dec 25 '19 at 19:30
The longest common prefix of `[“flip Clap Glop”]` is `”flip Clap Glop”`, not `””`. — rob mayoff, Dec 25 '19 at 20:15

Martin R · Answer 2 · 2018-01-26T08:05:33.457

String has already a commonPrefix(with:) method (if Foundation is imported), so one simple solution would be to "fold" that over the entire array of strings:

import Foundation

func longestCommonPrefix(of strings: [String]) -> String {
    guard let first = strings.first else { return "" }
    return strings.dropFirst().reduce(first) { $0.commonPrefix(with: $1) }
}

A more efficient solution, based on the idea in Find the longest common starting substring in a set of strings, is to

Find the smallest and largest string in the array.
Determine the common prefix of just those two strings.

func longestCommonPrefix(of strings: [String]) -> String {

    guard let first = strings.first else { return "" }

    var (minString, maxString) = (first, first)
    for str in strings.dropFirst() {
        if str < minString { minString = str }
        else if str > maxString { maxString = str }
    }

    return minString.commonPrefix(with: maxString)
}

Remarks:

An empty input array could be treated as a fatal error.
One could use min() and max() instead of the loop, but that would require two traversals of the string instead of one.

The longest common suffix can then be computed as the (reversed) longest common prefix of the reversed strings:

func longestCommonSuffix(of strings: [String]) -> String {
    let revStrings = strings.map { String($0.reversed()) }
    let revPrefix = longestCommonPrefix(of: revStrings)
    return String(revPrefix.reversed())
}

Examples:

print(longestCommonPrefix(of: ["A12[1]", "A13[1]", "A14[1]"])) // "A1"
print(longestCommonSuffix(of: ["A12[1]", "A13[1]", "A14[1]"])) // "[1]"

print(longestCommonPrefix(of: ["9-b", "10-b", "11-b"])) // ""
print(longestCommonSuffix(of: ["9-b", "10-b", "11-b"])) // "-b"

Your approach to the suffix won't work. Consider `["a0000", "b1111", "c0000"]`.Your algorithm produces the suffix `"0000"` but the correct answer is `""`. — rob mayoff, Jan 26 '18 at 01:19
@robmayoff: Oops, you are right – the strings have to be reversed *before* sorting. Should work now, thanks! — Martin R, Jan 26 '18 at 05:07
Also note that you must import Foundation to get the `commonPrefix(with:)` method. — rob mayoff, Jan 26 '18 at 08:03
@BartłomiejSemańczyk: You are welcome! – Btw, "too broad" is sometimes used as a closing reason for questions which just state a problem without showing any effort to solve it yourself. Instead of complaining inside the question I would recommend to update it with some attempt (which you surely made) and then vote to reopen it. — Martin R, Jan 26 '18 at 08:40

matt · Answer 3 · 2018-01-26T17:18:18.343

Perhaps the problem is merely one of imagining how one would ask whether all members of an array are equal?

extension Collection where Element : Equatable {
    var allEqual : Bool {
        let orig = self.first
        for elem in self {
            if elem != orig {
                return false
            }
        }
        return true
    }
}

Once you have that, you can just try prefixes of decreasing length starting with the length of the shortest string in the array:

func commonPrefix(_ arr:[String]) -> String {
    let prefixmax = arr.map {Int($0.count)}.min()!
    var prefix = ""
    for i in (1...prefixmax).reversed() {
        let prefixes = arr.map {$0.prefix(i)}
        if prefixes.allEqual {
            prefix = String(prefixes[0])
            break
        }
    }
    return prefix
}

let arr = ["A12[1]", "A13[1]", "A14[1]"]
let pref = commonPrefix(arr) // "A1"

Doing the same with the suffix is left as an exercise for the reader.

How to determine longest common prefix and suffix for array of strings?

3 Answers3