Day18 实现 strStr()

实现 strStr() 函数

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例1：

输入: haystack = "hello", needle = "ll"
输出: 2

示例2：

输入: haystack = "aaaaa", needle = "bba"
输出: -1

提示：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符

Java解法

思路：

• 第一次尝试：双指针;慢指针匹配当前匹配位置，快指针在第一位匹配成功时向后继续匹配，匹配完成跳出,然而超时了
• 超时优化：if (slow>haystack.length()-needle.length()) { break; }加上这个优化了下速度，但还是效率不高

package sj.shimmer.algorithm.ten_2;

/**
 * Created by SJ on 2021/2/11.
 */

class D18 {
    public static void main(String[] args) {
//        System.out.println(strStr("hello","ll"));
//        System.out.println(strStr("aaabb","bb"));
//        System.out.println(strStr("aaaaa","bba"));
//        System.out.println(strStr("",""));
        System.out.println(strStr("mississippi", "issip"));

    }
    public static int strStr(String haystack, String needle) {
        if (haystack == null) {
            return -1;
        }
        if (needle==null) {
            return -1;
        }
        if ("".equals(needle)) {
            return 0;
        }
        int slow = 0;
        int fast = 0;
        while (slow<haystack.length()){
            if (slow>haystack.length()-needle.length()) {
                break;
            }
            for (int i = 0; i < needle.length(); i++) {
                if (fast<haystack.length()&&haystack.charAt(fast)==needle.charAt(i)) {
                    if (i==needle.length()-1) {
                        return slow;
                    }
                    fast++;
                }else {
                    break;
                }
            }
            slow++;
            fast = slow;
        }
        return -1;
    }
}

image

官方解

https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/

1. 子串逐一比较 - 线性时间复杂度

   将长度为 L 的滑动窗口沿着 haystack 字符串逐步移动，并将窗口内的子串与 needle 字符串相比较，时间复杂度为 O((N - L)L)

   这个是每个长度的L都会比较，效率较差

   • 时间复杂度：O((N - L)L)
   • 空间复杂度：O(1)

2. 双指针 - 线性时间复杂度

   我使用的方法，但官方考虑的细节更多，效率稍微高一些

   class Solution {
     public int strStr(String haystack, String needle) {
       int L = needle.length(), n = haystack.length();
       if (L == 0) return 0;
   
       int pn = 0;
       while (pn < n - L + 1) {
         // find the position of the first needle character
         // in the haystack string
         while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn;
   
         // compute the max match string
         int currLen = 0, pL = 0;
         while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
           ++pn;
           ++pL;
           ++currLen;
         }
   
         // if the whole needle string is found,
         // return its start position
         if (currLen == L) return pn - L;
   
         // otherwise, backtrack
         pn = pn - currLen + 1;
       }
       return -1;
     }
   }
   

   感觉匹配不成功的回退处理做的更好

   • 时间复杂度：O((N - L)L)， 最优时间复杂度为 O(N)O(N)
   • 空间复杂度：O(1)

3. 其他优化

   • 大佬的KMP优化思想：needle中不存在的子串时实际上是可以不用回退那么多的，后续题刷多了总结下思想研究下