1
\$\begingroup\$

Solving the problem

Write a function that accepts a string of words with a similar prefix, separated by spaces, and returns the longest substring that prefixes all words. Sample input and output

The string “swift switch swill swim” should return “swi”. The string “flip flap flop” should return “fl”.

I have

import Foundation

func longestPrefix(of string: String) -> String {
    var longestPrefix = ""
    var prefixBeingChecked = ""
    
    let wordArray = string.components(separatedBy: " ")
    
    var firstWord = wordArray[0]
    
    for character in firstWord {
        prefixBeingChecked += String(character)
        
        for word in wordArray {
            if !word.hasPrefix(prefixBeingChecked) {
                return longestPrefix
            }
        }
        
        longestPrefix = prefixBeingChecked
    }
    
    return longestPrefix
}

print(longestPrefix(of: "swift switch swill swim"))

But I'm not sure how I might improve on the quadratic time complexity. What would be a good way to improve performance?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ While it's great that a review enabled you to improve your code, please do not update the code in your question to incorporate feedback from answers. Doing so goes against the Question + Answer style of Code Review, as it unfortunately invalidates the existing review(s). This is not a forum where you should keep the most updated version in your question, so I rolled your changes back to the previous version. Please see see what you may and may not do after receiving answers for ways to announce your new code. \$\endgroup\$
    – Martin R
    Commented Mar 31, 2022 at 21:44
  • \$\begingroup\$ Oops, I only did since I couldn't format multi-line code in a comment. Noted. \$\endgroup\$
    – Jakory
    Commented Mar 31, 2022 at 21:46
  • 1
    \$\begingroup\$ Btw, your new method (sorting by string length) does not work, try it with the input string "abc abxx abcdefg". Also sorting requires O(n*log(n)) operations, which is worse than a single traversal. \$\endgroup\$
    – Martin R
    Commented Mar 31, 2022 at 21:47

1 Answer 1

2
\$\begingroup\$

Some remarks:

let wordArray = string.components(separatedBy: " ")

produces an array of strings. A slightly more memory-efficient method is

let wordArray = string.split(separator: " ")

which produces an array of Substrings which share the character storage with the original string.

The variable

var firstWord = wordArray[0]

is never mutated and should be defined as a constant with let. If we use split(separator:) then the array can be empty:

guard let firstWord = wordArray.first else {
    return ""
}

In the inner loop

for word in wordArray { ... }

it is not necessary to check against the first word in the list, so one can replace that by

for word in wordArray.dropFirst() { ... }

Is is not common practice in Swift to make the type part of the variable name, so I would replace wordArray by, e.g., words.

A more efficient algorithm

A more efficient solution has been described in Find the longest common starting substring in a set of strings on Stack Overflow, see also How to determine longest common prefix and suffix for array of strings? on Stack Overflow:

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

The first part requires only a linear traversal of the array, plus the cost of the string comparisons.

There is a dedicated method commonPrefix(with:) for the second part.

This leads to the following implementation:

func longestCommonPrefix(of string: String) -> String {
    
    let words = string.split(separator: " ")
    guard let first = words.first else {
        return ""
    }

    var (minWord, maxWord) = (first, first)
    for word in words.dropFirst() {
        if word < minWord {
            minWord = word
        } else if word > maxWord {
            maxWord = word
        }
    }

    return minWord.commonPrefix(with: maxWord)
}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.