Simple Java solution with explanation


  • 0
    L

    Since it is part of "easy", it may not require a KMP solution I think. A simple O(m*n) solution should be good enough in this case.

    Consider two Strings "abcd" and "cd". You would want to run a loop to run it for "abcd".length() - "cd".length() times to do comparisons between the haystack and the needle. The worst case comparison will be O(mn) when it may be like "cccc" and "cd". Generally this algorithm should be good enough for this problem: However, an alternative is to use KMP that is more like O(m+n) solution.

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

Log in to reply
 

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