Implement strStr() Problem


Description

LeetCode Problem 28.

Implement strStr().

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

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().

Example 1:

1
2
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:

1
2
Input: haystack = "", needle = ""
Output: 0

Constraints:

  • 0 <= haystack.length, needle.length <= 5 * 10^4
  • haystack and needle consist of only lower-case English characters.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int strStr(string haystack, string needle) {
        int l1 = haystack.size(), l2 = needle.size();
        int i = 0, j = 0, k = 0;
        if (l2 == 0)
            return 0;
        if (l1 == 0)
            return -1;
        bool isSub = true;
        while (i < l1 - l2 + 1) {
            if (haystack[i] == needle[0]) {
                isSub = true;
                for (k = 0; k < l2; k ++) {
                    if (haystack[i + k] != needle[k]) {
                        isSub = false;
                        break;
                    }
                }
                if (isSub)
                    return i;
            } 
            i ++;
        }
        return -1;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...