Java Solution; ~O(n^2) running time, O(1) memory, 11ms.


  • 0
    S
    public class Solution {
      public int strStr(String haystack, String needle) {
        // if cheating is allowed: 
        // return haystack.indexOf(needle);
    
        final int hl = haystack.length();
        final int nl = needle.length();
    
        if (nl > hl) return -1;
        if (nl == 0) return 0;
    
        for (int i = 0; i < hl; i++) {
          if (haystack.charAt(i) == needle.charAt(0) && (hl - i) >= nl) {
            boolean substring = true;
            for (int j = 1, k = i + 1; j < nl; j++, k++) {
              if (haystack.charAt(k) != needle.charAt(j)) {
                substring = false;
                break;
              }
            }
            if (substring) return i;
          }
        }
    
        return -1;
      }
    }
    

Log in to reply
 

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