Solution by rohitnandi12

• Primary Thougths
There are multiple approaches to solve this problem. If you are thinking of using a library function, that will do but it will not help you in the long run. Ask yourself, Do you want to be a script kiddie rest of your life or be a hard core developer?

Test Cases
Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

``````Test Inputs
haystack =  "what is it"

What will be the output when "needle" is
T1 : ""       // output : "0"
T2 : "it"     // output : "8"
T3 : "It"     //output : "-1"
T3 : "ita"     //output : "-1"
T3 : "was"     //output : "-1"
``````

Approach #1 Implementation [Accepted]

Intuition

To detect needle in haystack I will start looking from the beginning. Stop where the character in haystack matches with first character of needle. Look for the next following characters in haystack, if it matches to needle I got my first index else I will keep on looking until i reach the end of haystack.

Algorithm

• Iterate c over haystack
• If c matches the first character of needle
• Look for the next following characters in haystack if it matches the rest of the characters of needle
• Return c index
• Return -1

Java Solution

``````class Solution {
public int strStr(String haystack, String needle) {

if(needle.length()==0)return 0;

for(int i=0; i< haystack.length()-needle.length()+1; i++){

if(haystack.charAt(i)==needle.charAt(0)){
if(needle.equals(haystack.substring(i,i+needle.length()))){
return i;
}
}
}
return -1;
}
}

``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

• Space complexity : \$\$O(1))\$\$.

Thank You. Happy Coding :-)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.