28. Implement strStr() (https://leetcode.com/problems/implement-strstr/submissions/): Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

28. Implement strStr() (#1 Two Pointers).java

// Two pointer solution: one pointer for each array
// Time：O(m * n) where m is the length of haystack and n is the length of needle, 3ms
// Space: O(1), 37mb
class Solution {
    public int strStr(String haystack, String needle) {
        // Corner case
        if(needle.length() == 0) return 0;
        
        // hp points to char in haystack, np points to char in needle
        for(int hp = 0, np = 0; hp < haystack.length(); hp++) {
            if(haystack.charAt(hp) == needle.charAt(np)) {
                // If there is a matching, move both hp and np
                np++;
                
            } else if(np != 0) {
                // If partially matching then failed, neeed to move back hp
                hp = hp - np;
                np = 0;
            }
            
            // If whole needle is found, return index
            if(np == needle.length()) {
                return hp - np + 1;
            }
        }
        
        // Not found
        return -1;
    }
}

28. Implement strStr() (#2 Nesting loop).java

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0) return 0;  //Delete this or "missing return statement"
        for(int h = 0; h < haystack.length(); h++) {  //haystack pointer doesn't move when checking needle
            for(int n = 0; n < needle.length(); n++) {
                if(h + n >= haystack.length()) return -1;
                if(haystack.charAt(h + n) != needle.charAt(n)) break;
                if(n == needle.length() - 1) return h;
            }
        }
    }
}

28. Implement strStr() (#3 Nesting loop).java

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;
        }
      }
    }
}