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