Friday, July 25, 2014

Implement strStr()

Implement strStr().

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

KMP和RK会在以后补上。暴力方法:
public class Solution {
    //Time: O(m*n)  Space: O(1)
    public String strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return null;
        }
        if (needle.length() == 0) {
            return haystack;
        }
        
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int length = 0;
            for (int j = i; j < needle.length() + i; j++) {
                if (haystack.charAt(j) == needle.charAt(j - i)) {
                    length++;
                } else {
                    break;
                }
                if (length == needle.length()) {
                    return haystack.substring(i);
                }
            }
        }
        return null;
    }
}

No comments:

Post a Comment