strStr and Coding Style

Problem

Easy 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.

Have you met this question in a real interview? Yes Example If source = "source" and target = "target", return -1.

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

Challenge O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Clarification Do I need to implement KMP Algorithm in a real interview?

Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first.

Thoughts

KMP算法利用了pattern match思想，通过维护next数组达到减少回退次数的目的。 不过本题主要是考察coding style和bug free. 用直观的两次循环即可

Code

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

        return -1;
    }
}

Analysis

两重循环，最坏的情况下是最后才找到或找不到，时间复杂度O(mn).

注意target.length() == 0应该永远返回０。

需要注意的点：

1. 外循环的终止条件应当为i <= source.length() - target.length()，=号不要忘

2. 当target长度为0时，应返回0.