[leetcode] 28. Implement strstr ()

28、 Realization strStr()

subject ：

Realization strStr() function .

Here are two strings haystack and needle , Please come in haystack Find in string needle The first place the string appears （ Subscript from 0 Start ）. If it doesn't exist , Then return to -1 .

explain ：

When needle When it's an empty string , What value should we return ？ This is a good question in an interview .

For this question , When needle When it's an empty string, we should return 0 . This is related to C Linguistic strstr() as well as Java Of indexOf() The definition matches .

Example 1:

 Input ：haystack = "hello", needle = "ll"
 Output ：2

Example 2:

 Input ：haystack = "aaaaa", needle = "bba"
 Output ：-1

Their thinking ：

This question can be used Violent match ： To solve

We can make the string needle And string haystack All the lengths of are m All substrings of match once .

To reduce unnecessary matching , Every time we fail to match, we immediately stop the matching of the current substring , Continue matching for the next substring . If the current substring matches successfully , We can return the starting position of the current substring . If all substrings fail to match , Then return to −1.

Reference code ：

class Solution {
    
    public int strStr(String haystack, String needle) {
    
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
    
            boolean flag = true;
            for (int j = 0; j < m; j++) {
    
                if (haystack.charAt(i + j) != needle.charAt(j)) {
    
                    flag = false;
                    break;
                }
            }
            if (flag) {
    
                return i;
            }
        }
        return -1;
    }
}