Solution by rohitnandi12


  • 0
    R

    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 :-)


Log in to reply
 

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