Brute force find words with prefix

import Foundation
import PlaygroundSupport

func wordsWith(prefix: String, in dictionary: [String]) -> [String] {
    var output: [String] = []
    let prefixCount = prefix.count
    let prefixCharArray = Array(prefix)
    wordLoop: for word in dictionary {
        let charArray = Array(word)
        var wordIndex = 0
        var prefixIndex = 0
        while prefixIndex < prefixCount {
            if charArray[wordIndex] != prefixCharArray[prefixIndex] {
                continue wordLoop
            }
            wordIndex += 1
            prefixIndex += 1
        }
        output.append(word)
    }
    return output
}
let dictionary = ["CAT", "DOG", "BUNNY", "CAN", "CUT", "DOLL"]
print(wordsWith(prefix: "CA", in: dictionary))

How would you improve this code? Strings in Swift have a hasPrefix() function on them but since this is for an interview problem you cannot use it.

Totally a nit, ‘dictionary’ is an Array

In my actual project, we need to search elements from a list and the search logic needs to match the "beginning" of the strings in the list with the user's input:

let filteredObjects = objects?.filter {
                $0.value?.lowercased().starts(with: searchString.lowercased()) ?? false
}

I can't show the unit tests but the QA approved :D

Is case sensitivity a requirement? I’m assuming you only care about upper case, but wanted to double check.

If one of the words you’re testing has a length less than the length of the prefix I think it will crash

I would ignore the comments about case sensitivity, since insensitive comparisons might break the algorithm on lots of real world input. I think a review would depend on the goal of the exercise if you are trying to implement most of the algorithm yourself the two cursors are probably how contains or startsWith are implemented. So that's fine. To remove the label you can try a forEach

Using the return statement in the body closure will exit only from the current call to body, not from any outer scope, and won't skip subsequent calls.

Once you have it down to a forEach that populates a single return value that's often simplified down to a reduce or filter

@aaroncrespo, considering case sensitivity is 100% valid. To decide how to handle case sensitivity is a design decision, probably shouldn’t assume anything about input data until clarified.

I would ignore the comments about case sensitivity since insensitive comparisons might break the algorithm on lots of real-world input. I think a review would depend on the goal of the exercise if you are trying to implement most of the algorithm yourself the two cursors are probably how contains or startsWith are implemented. So that's fine. To remove the label you can try a forEach

Agree. If the scope of the exercise is to don't use any existing functions from Swift, of course, my solution is not valid.

I'd separate this one big function into two small functions. Part of your original function is a loop through dictionary, and part is checking strings to see if they have a prefix. I like to have many functions that each only do one thing. So I'd probably make the prefix-checking part into an extension on String, and make the "loop through dictionary and return some elements" into a simple filter! I think breaking functions into smaller functions makes it easier to read.

I also noticed the inner while loop started both variables wordIndex and prefixIndex at 0 and incremented them both once per loop. This means both variables always have the same value, so you can just use a single variable. And because they get incremented once per loop, with a known start and end value, you can just replace the while loop with a for loop.

import Foundation
import PlaygroundSupport

func wordsWith(prefix: String, in dictionary: [String]) -> [String] {
    return dictionary.filter{ $0.has(prefix) }
}

extension String {
    func has(_ prefix: String) -> Bool {
        let prefixCharArray = Array(prefix)
        let charArray = Array(self)
        for i in 0..<prefix.count {
            if charArray[i] != prefixCharArray[i] {
                return false
            }
        }
        return true
    }
}

let dictionary = ["CAT", "DOG", "BUNNY", "CAN", "CUT", "DOLL"]
print(wordsWith(prefix: "CA", in: dictionary)) // CAT, CAN

Writing from the top of my head on my cellphone, I might have misunderstood but I think the above code is equivalent to:

print(dictionary.filter(where: { $0.hasPrefix(“CA”) }

My bad, hadn’t seen the comment above about this being an interview problem.

Interviews like this often focus on two things:

• writing the code yourself without aide from library functions (no filter, no hasPrefix, etc)
• code complexity (Big O)

In regards of complexity, the goal would be to implement this without quadratic growth, this is, avoiding O(n2). Could this be implemented in O(n log n)? Could this be linear O(n)?

I believe those are the questions interviewers will be looking for you to answer.

Another thing interviewers could be looking for is common errors like index out of bounds, etc. The code examples above assume the words in the dictionary are longer or equal to the prefix.

What would your code do if the dictionary contained “A” or “”?

If we need to implement hasPrefix ourselves, then I feel like the zip function would work well here as a good way to iterate through the two strings character by character without having to manually deal with tracking and updating indices.

It eliminates having to worry about the index out of bounds errors that @eneko brought up and still works in situations where the prefix is longer than the word since the zip function will stop when one of the sequences it is supplied as input has no more remaining elements.

There is also an added benefit that it allows for a more generic extension on Sequence. If we are manually subscripting and tracking the indices as an Int, then the most generic we could get would be an extension on Collection with a where clause specifying that the collection's Index is an Int.

The only problem I see with this custom implementation of hasPrefix is if the function must be case insensitive. Since the only requirement of this extension is that the Element conforms to Equatable we'd have to further constrain Element to get access to the lowercased() method.

extension Sequence where Element: Equatable {
    func hasPrefix<Prefix: Sequence>(_ prefix: Prefix) -> Bool where Element == Prefix.Element {
        for (element, prefixElement) in zip(self, prefix) {
            if element != prefixElement {
                return false
            }
        }
        return true
    }
}

extension Sequence where Element == String {
    func wordsWith(prefix: String) -> [String] {
        return filter { $0.hasPrefix(prefix) }
    }
}

let dictionary = ["CAT", "DOG", "BUNNY", "CAN", "CUT", "DOLL"]
dictionary.wordsWith(prefix: "CA") // CAT, CAN