Thursday, September 27, 2012

[Leetcode] Implement strStr



Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Thoughts:
1. The most straight thought is to iterate through the haystack.

2. 另外一个为kmp算法,讲解可以参考 topcoder

Java Code:
public String strStr(String haystack, String needle) {
         if(needle.length() == 0) return haystack;
         
         int n = 0;
         
         for(int i = 0; i <= haystack.length() - needle.length(); i++){
             n = 0;
             
             while(n < needle.length() && haystack.charAt(i+n) == needle.charAt(n))
                  n++;
                  
             if(n == needle.length()) return haystack.substring(i);
         }
         
         return null;
    }

No comments:

Post a Comment