Simple Java O(n) one pass


  • 0
    N
    public int strStr(String haystack, String needle) {
            if(haystack == null || needle == null || haystack.length() < needle.length()){
                return -1;
            }
            if(needle.equals("")){
                return 0;
            }
            int j = 0, idx = -1;
            for(int i=0; i<haystack.length() && j < needle.length();){
                if(needle.charAt(j) == haystack.charAt(i)){
                    if(j == 0){
                        idx = i;
                    }
                    j++;
                }else{
                    if(idx != -1){
                        j = 0;
                        i = idx;
                        idx = -1;
                    }
                }
                i++;
            }
            if(j == needle.length()){
                return idx;
            }else{
                return -1;
            }
        }

  • 0

    This is brute force O(mn), not O(n). You'd need something like Knuth–Morris–Pratt algorithm for O(m+n), and it's obviously impossible to solve this in O(n) because you need to inspect both strings.


Log in to reply
 

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