Implementing strStr() in Swift; breaking early

A classic problem often used in coding interviews (and is problem 28 on LeetCode) is:

to create a function that takes two strings s1 and s2 as arguments, and find the Integer representing the location of the first occurrence of the sub-string s2 in the string s1.

[Since you asked (and so nicely), the arguments s1 and s2 consist of lowercase English alphabetic letters ascii[a-z], and either (or both) of s1 and s2 can be the empty string “”]

Swift is a powerful language, and surely we can leverage inbuilt functions to quickly solve this little problem. Now the Swift String API has changed over time (and can be a little tricky) but this is not beyond the wit of man.

A simple solution — Swift

s1.range(of: s2)

This returns an optional Range<String.Index>? which is kind of what we want, but the lowerbound and encoded into an Int. Can?

Using Swift to locate S2 in S1

Since we return an optional range, we use if let to prevent any awkward crashes. But wait, if s1 and s2 are empty there should be a match (“” matches “” at position 0!). Looks like a good use for a guard statement in Swift.

We could also choose to use NSRange for this, arguably making it easier to read by allowing use of the location property of NSRange.

Using Swift to locate S2 in S1

However, if you run either of these two implementations using larger inputs you find that it runs Unacceptably slowly. If you run through LeetCode you will get the dreaded “Time Limit Exceeded” message.

This is because you can do better. Much better.

Walking the array — Theory

Instead of allowing Swift at a high level to do the work for us, we can walk through the S1 and see if we have a match with S2.

Using s1=acacat and s2=cat we can show an example.

The initial strings

Which has a high level algothms of comparing s1[0] to s2[0]. If we don’t have a match, we move to comparing s1[1] with s2[0] and so on.

High level algorithm

Match iteration 1 — matching with s[0]

Obviously we cannot have a complete match, so we don’t need to check the rest of s2.

The initial comparison between s1 and s2, s1[0] and s2[0]

Match iteration 2 — matching with s[1]

The first element of s2 (s2[0])

So we can move to the next element of s1

The second comparison between s1 and s2, s1[1] and s2[0]

s1[1] = s2[0]

The second element of s2 (s2[1])

The second comparison also matches!

Comparing s1 and s2, s1[2] and s2[1]

The third element of s2 (s2[2])

Comparing s1 and s2, s1[3] and s2[2]

Here we do not match, and s1[1] does not have a complete match with s[1]

Match iteration 3 — matching with s1[2]

The first element of s2 (s2[0])

Comparing s1 and s2, s1[2] and s2[0]

Unfortunately s1[2] does not match with s2[0]

Match iteration 4 — matching with s1[3]

The first element of s2 (s2[0])

Comparing s1 and s2, s1[3] and s2[0]

We have a match!

The second element of s2 (s2[1])

Move to the next element of s1 and s2

Comparing s1 and s2, s1[4] and s2[1]

The third element of s2 (s2[2])

Here we have a full match!

Comparing s1 and s2, s1[5] and s2[2]

Things to know — Don’t go too far

We actually do not need to walk through every element of s1, we actually only need to look through the elements s1.count — s2. count because we obviously need to fit s2 into the remaining space in s1.

It does not make sense to check beyond the end of the array

So if s1 = “checks” and s2 = “aaa” we only need to check the first 4 elements of s1 against s2. This is because s1.count = 6 and s2.count = 3, and we walk from the first element of s1[0] to s1.count — s2.count.

The last position that needs to be counted, calculated by s1.count — s2.count

This leads us to have the main loop for our code in Swift

Creating the main loop in Swift

Now we can use a great feature of swift to check for matches…

A better solution — ArraySlice

If we convert s1 and s2 into arrays of character in Swift, we can subscript them with integers.

We compare the element of s1[i], and create an ArraySlice from i to i + s2.count -1 (remember that arrays are zero indexed, so we need to add the “-1” here) and if it matches s1 we are done (which has to be cast to an array to match).

The length of s2 cannot be longer than s1, or we will by definition not have a match!

Implementation of strStr using ArraySlice

Another solution — Two pointers

Are you mad? You want to use a separate pointer for s2, even though you know that we need to walk ahead of i a standard number? You want to use a while loop for i? Ok…we can use a second pointer for j that walks the s2 String.

We know that we have finished if j is equal to the length of s2String, remembering that the string is zero indexed, so is actually written as:

j == s2Array.count — 1

Ok, can.

Implementation of strStr using two pointers

Another solution — walk the s2 array

Want to stay away from Array Slices? Even better you can break early to save some valuable time!

Implementation of strStr walking the second array

What do you think? Is breaking early that important?