Leetcode question brushing: String 06 (implement strstr())

28. Realization strStr()

Force button topic link

Realization strStr() function .

Given a haystack String and a needle character string , stay haystack Find in string needle The first place the string appears ( from 0 Start ). If it doesn't exist , Then return to -1.

Example 1:
Input : haystack = “hello”, needle = “ll”
Output : 2

Example 2:
Input : haystack = “aaaaa”, needle = “bba”
Output : -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 .

Originally, I wanted a string pattern matching algorithm KMP Algorithm , I didn't write it , harm .

package com.programmercarl.string;

/** * @ClassName StrStr * @Descriotion TODO * @Author nitaotao * @Date 2022/6/25 15:52 * @Version 1.0 * https://leetcode.cn/problems/implement-strstr/ *  Realization  strStr() **/
public class StrStr {
    
    public static void main(String[] args) {
    
        System.out.println(strStr("bababbababbbabbaa", "" +
                "abbba"));
    }

    /** *  String pattern matching algorithm  *  Except in special cases  * 1.  Traverse a large string  * 2.  Traversal string  *  When the current character of the small string is the same as that of the large string , Compare next , If they are equal all the way to the end , return  *  If you encounter unequal , Then the big string moves back n position  * n For the next bit in the string that is the same as the initial letter  * * @param haystack * @param needle * @return */
    public static int strStr(String haystack, String needle) {
    
        // Judge special cases 
        if ("".equals(needle)) {
    
            return 0;
        }

        if (haystack.length() < needle.length()) {
    
            return -1;
        }

        int bigIndex = 0;

        // In string offset 
        int offset = 0;
        while (bigIndex < haystack.length()) {
    
            while (needle.charAt(offset) == haystack.charAt(bigIndex + offset)) {
    
                // Both sides move back and continue to compare 
                if (offset == needle.length() - 1) {
    
                    return bigIndex;
                } else {
    
                    offset++;
                }
                // The string ends 
                if (bigIndex + offset > haystack.length() - 1) {
    
                    break;
                }
            }
            bigIndex++;
            offset = 0;
        }
        return -1;
    }
}