[LintCode] 13 strStr

Description
For a given source string and a target string, you should output the first index(from 0) of target string in source string.
If target does not exist in source, just return -1.


Example
If source = "source" and target = "target", return -1.
If source = "abcdabcdefg" and target = "bcd", return 1.


思路
最简单的就是Brute-Force一下。用两重循环来做。
source长度为N，target长度为M。
外循环用i来表示source里需要匹配的位置。
从这个位置开始第内循环，j表示target中需要匹配的位置。
内循环出来如果每一位都匹配上了，j的值就是M，因为每次匹配上j都加1。这时候表示找到了。
worst-case时间复杂度是 O(MN)，空间复杂度是O(1)。

更快的做法参见strStr II。


Code

class Solution {
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    public int strStr(String source, String target) {
        // write your code here
        if (source == null || target == null) {
            return -1;
        }
        
        int N = source.length();
        int M = target.length();
        
        if (M == 0) {
            return 0;
        }
        
        for (int i = 0; i <= N - M; i++) {
            int j = 0;
            for (; j < M; j++) {
                if (source.charAt(i + j) != target.charAt(j)) {
                    break;
                }
            }
            if (j == M) {
                return i;
            }
        }
        
        return -1;
    }
}