Swift Coding Test Course, String Search

Hello! In this post, we will solve a problem of finding a string using Swift. String problems are common in coding tests, and they greatly help in understanding efficient search algorithms and string processing methods. Through this course, we will solidify our foundation in string processing.

Problem Description

Here is a string search problem:

Given a string haystack and needle, write a function to find the index of the first occurrence of needle in haystack. If needle does not exist, it should return -1.

Examples:

  • haystack = "hello", needle = "ll" => Output: 2
  • haystack = "aaaaa", needle = "bba" => Output: -1
  • haystack = "", needle = " => Output: 0

Problem Approach

To solve this problem, we need to compare the strings sequentially to check where needle appears in haystack. We can follow these steps:

  1. First, check the length of needle and compare it with the length of haystack to determine if needle can exist in haystack.
  2. Then, extract substrings of the length of needle from each index of haystack and compare them.
  3. If the comparison matches, return the index; otherwise, return -1.

Swift Code Implementation

Now, let’s implement the above logic in Swift:

func strStr(_ haystack: String, _ needle: String) -> Int {
        let haystackCount = haystack.count
        let needleCount = needle.count

        // Return 0 when needle is empty
        if needleCount == 0 {
            return 0
        }

        // Return -1 if the length of haystack is shorter than needle
        if haystackCount < needleCount {
            return -1
        }

        // Convert haystack to an array
        let haystackArray = Array(haystack)

        // Compare substring with needle at each index
        for i in 0...(haystackCount - needleCount) {
            var j = 0

            while j < needleCount && haystackArray[i + j] == needle[needle.index(needle.startIndex, offsetBy: j)] {
                j += 1
            }

            // If needle is found
            if j == needleCount {
                return i
            }
        }

        // If needle is not found
        return -1
    }

Code Explanation

Now let’s explain the code in detail:

  • func strStr: A function that takes two strings haystack and needle as arguments and performs the string search.
  • let haystackCount = haystack.count: Stores the length of haystack.
  • let needleCount = needle.count: Stores the length of needle.
  • if needleCount == 0: If needle is empty, return 0.
  • if haystackCount < needleCount: If the length of haystack is shorter than needle, return -1 as it cannot be found.
  • let haystackArray = Array(haystack): Converts the string into an array to allow access to each character.
  • for i in 0...(haystackCount - needleCount): Iterates through all indices of haystack. The loop should consider the length of needle for the search range.
  • The inner while loop compares the substring from needle with haystack at each index.
  • If all comparisons match, it returns index i.
  • Finally, it returns -1 if needle is not found.

Test Cases

Let’s write some test cases to validate this code:

print(strStr("hello", "ll"))   // Output: 2
print(strStr("aaaaa", "bba"))     // Output: -1
print(strStr("", ""))              // Output: 0
print(strStr("abcde", "abc"))      // Output: 0
print(strStr("abcde", "xyz"))      // Output: -1

Conclusion

In this lesson, we learned how to solve a string finding problem using Swift. It’s important to carefully check the length of the strings, compare substrings, and define the search range to solve the given problem. String-related problems have various variations, so ensure to practice to handle more diverse cases.

In the next lesson, we will cover another type of string problem. Thank you!