Implement strStr() in Java - LeetCode

Problem : Implement strStr().

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




Java Solution 1:


public class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack==null || needle==null)
           return -1;
        if(haystack.length()==0 && needle.length()==0)
           return 0;
        return haystack.indexOf(needle);    
    }
}


Time Complexity : O(n)   Space Complexity : O(n)


Java Solution 2:




public class Solution { 
 public int strStr(String haystack, String needle) {
   for (int i = 0; ; i++) {
      for (int j = 0; ; j++) {
         if (j == needle.length())
             return i;
         if (i + j == haystack.length()) 
             return -1;
         if (needle.charAt(j) != haystack.charAt(i + j)) 
             break;
   }
  }
 }
}

Time Complexity : O(n^2)  Space Complexity : O(n)



Please mention in comments if you have any other solution.



About The Author

Subham Mittal has worked in Oracle for 3 years .
For more java articles ,Click here to Subscribe JavaHungry