Implement the strStr() function

Subject address: leetcode-cn.com/problems/im…

Given a Haystack string and a Needle string, find the first position in the Haystack string where the Needle string appears (starting from 0). If none exists, -1 is returned.

Example 1:

Enter: haystack ="hello", needle = "ll"Output:2
Copy the code

Example 2:

Enter: haystack ="aaaaa", needle = "bba"Output: -1
Copy the code

Description: What value should we return when needle is an empty string? This is a good question to ask in an interview. For this case, we should return 0 when needle is an empty string. This is consistent with the C language STRSTR () and the Java definition of indexOf().

Solution 1: violent solution

To implement an indexOf function, the first thing that comes to mind is to compare two Pointers in two strings.

The violent solution (BF) scans in sequence and if there is the same synchronization continues and there is a difference it breaks, the pattern string goes back to the starting point and the main string goes back to the next starting point. That is, the length of the main string is traversed, and the rest depends on when the pattern string is broken. In the worst case, every pattern string traverses until the last break is matched at the end of the main string and that’s O(n*m)

The border

  • The index of crossing the line

details

  • End of loop condition
  • Haystack null returns 0
  • Haystack returns -1 less than Needle
public int strStr(String haystack, String needle) {
    char[] hay = haystack.toCharArray();
    char[] need = needle.toCharArray();
    int h = hay.length;
    int n = need.length;
    int i=0,j=0;
    while(j < h && i < n){
        if(hay[j] == need[i]){
            i++;
            j++;
        }else {
            j=j-i+1;
            i=0; }}if(i >= n) return j-i;
    else return -1;
}
Copy the code

Solution two: intercept the substring

In addition to the comparison of two Pointers in turn, determine whether a string contains another string directly to sequentially intercept the substring of the target length, determine whether there are equal substrings. So I’m going to take the substring method that I’m using directly, and I’ve done this a couple of times, and I’m going to write it the same way but we really need to know what the implementation looks like in order to get an objective sense of its complexity, and in this case it’s a traversal. Therefore, the solution of the following code is also a two-level traversal

public int strStr(String haystack, String needle) {
    int n = needle.length(); 
    int h = haystack.length();
    for (int i = 0; i < h - n + 1; i++) {
        if (haystack.substring(i, i + n).equals(needle)) {
            returni; }}return -1;
}
Copy the code

In fact, this solution is exactly the same as method one except that method one writes the intercept and comparison directly, and it’s better than method one except that it doesn’t traverse the short part of it and one is h * (?). The other one is h minus n plus 1 times? Because you can write two layers of traversal separately. The outside iterates over the beginning of the substring, and the inside iterates over whether the substring is equal to the pattern string. And solution one goes in a loop

conclusion

String matching algorithm is a more classical algorithm, but also in the field of computer practical application of the algorithm. Both solution 1 and solution 2 above are actually full ergodic comparisons. Many scientists have invented more ways to reduce the number of comparisons, such as RK algorithm, BM algorithm and KMP algorithm. These are not covered here for the moment. There will be separate articles on this and other algorithms in other series.