Posts Implement StrStr (InterviewBit)
Post
Cancel

Implement StrStr (InterviewBit)

PROBLEM DESCRIPTION

Implement strStr().

strstr - locate a substring ( needle ) in a string ( haystack ).

Try not to use standard library string functions for this question.

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

NOTE: String A is haystack, B is needle.

Good clarification questions:

  • What should be the return value if the needle is empty?
  • What if both haystack and needle are empty?

For the purpose of this problem, assume that the return value should be -1 in both cases.

SOLUTION

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
28
29
30
31
32
33
public class Solution {

    public int strStr(final String A, final String B) {

        //A -> haystack
        //B -> needle

        int n = A.length();
        int m = B.length();

        if(n == 0 || m == 0 || m > n){
            return -1;
        }

        // check if we can get the needle if we start from index i of haystack
        for(int i=0; i+m <= n; i++){

            int idx = 0;

            while(idx < m && A.charAt(idx+i) == B.charAt(idx)){
                idx++;
            }

            if(idx == m)
                return i;


        }

        return -1;

    }
}
This post is licensed under CC BY 4.0 by the author.