Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or-1if needle is not part of haystack.

Example 1:

Input:
 haystack = "hello", needle = "ll"

Output:
 2

Example 2:

Input:
 haystack = "aaaaa", needle = "bba"

Output:
 -1

Clarification:

What should we return whenneedleis an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 whenneedleis an empty string. This is consistent to C's strstr() and Java's indexOf().

Analysis

字符串匹配问题，直觉的实现就是以needle为pattern string，在haystrack循环遍历0, ..., n - m + 1, 若找到对应则返回index。

O(n^2) time, O(1) space

KMP算法

略

Solution

Two loops

public int strStr(String s, String t) {
        if (t.isEmpty()) return 0; // edge case: "",""=>0  "a",""=>0
        for (int i = 0; i <= s.length() - t.length(); i++) {
            for (int j = 0; j < t.length() && s.charAt(i + j) == t.charAt(j); j++)
                if (j == t.length() - 1) return i;
        }
        return -1;
    }

Use needle as pattern string, outer loop move n - m + 1 times, inner loop at most m times

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }
        if (haystack == null || haystack.isEmpty()) {
            return -1;
        }
        int n = haystack.length();
        int m = needle.length();

        for (int i = 0; i < n - m + 1; i++) {
            if (matches(haystack.substring(i, i + m), needle)) {
                return i;
            }
        }

        return -1;
    }
    private boolean matches(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

Multiple Pointers - O(mn) time

public class Solution {
    /**
     * @param source: 
     * @param target: 
     * @return: return the index
     */
    public int strStr(String source, String target) {
        // Write your code here
        if (target.equals("")){
            return 0;
        }
        for (int i = 0; i < source.length() - target.length() + 1; i++){
            int j = 0;
            int k = i;
            while (j < target.length() && k < source.length()){
                if (source.charAt(k) == target.charAt(j)){
                    k++;
                    j++;
                } else {
                    break;
                }
            }
            if(j == target.length()){
                return k - target.length();
            }
        }
        return -1;
    }
}

Using string equals

public int strStr(String haystack, String needle) {
    if(needle.equals("")) return 0;
    int L = needle.length();
    for(int i=0; i<=haystack.length()-L; i++) 
        if(haystack.substring(i,i+L).equals(needle)) return i;
    return -1;
}