Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1:

Input: haystack = “hello”, needle = “ll”
Output: 2

Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1

Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

strStr() implementation in C++

The implementation should consider the corner cases, when the needle is empty, the result should be always 0. The following implementation of strStr() method in C++ has a time complexity O(MN) where M and N are the lengths of the input haystack and needle string.

The outer loop should be from 0 to the length of M-N+1. And the inner loop checks if the substring of haystack matches the needle. This is not the optimial solution as there will be a KMP algorithm which requires a pre-computation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int strStr(string haystack, string needle) {
        for (int i = 0; i + needle.size() - 1 < haystack.size(); ++ i) {
           bool ok = true;
           for (int j = 0; j < needle.size(); ++ j) {
              if (haystack[i + j] != needle[j]) {
                  ok = false;
                  break;
              }   
           }
           if (ok) return i;
        }
        return (needle.size() == 0) ? 0 : -1;
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        for (int i = 0; i + needle.size() - 1 < haystack.size(); ++ i) {
           bool ok = true;
           for (int j = 0; j < needle.size(); ++ j) {
              if (haystack[i + j] != needle[j]) {
                  ok = false;
                  break;
              }   
           }
           if (ok) return i;
        }
        return (needle.size() == 0) ? 0 : -1;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —