[LeetCode]28.实现strStr()(Java)

原题地址: implement-strstr

题目描述:

实现 strStr() 函数。

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

说明:

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

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

示例 1:

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

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

输入:haystack = "", needle = ""
输出:0

提示:

0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成

解答方法:

1.

class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack.equals("")&&needle.equals(""))return 0;
        if(haystack.equals("")&&!needle.equals(""))return -1;
        int sum = 0;
        boolean flag = false;
        int length = haystack.length() - needle.length() + 1;
        while(sum <= length){
            if(haystack.startsWith(needle)){
                flag = true;
                break;
            }else{
                sum++;
                if(haystack.length()>1)
                haystack = haystack.substring(1);
            }
        }
        if(flag == false)sum = -1;
        return sum;

}}

[LeetCode]28.实现strStr()(Java)

感觉这样不走心的刷题好没意义呀!下次一定对着优秀的解法好好复习复习,哭!

2.评论中解法

class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格,使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组,数组长度为匹配串的长度(next 数组是和匹配串相关的)
        int[] next = new int[m + 1];
        // 构造过程 i = 2,j = 0 开始,i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话,j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话,先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i],结束本次循环,i++
            next[i] = j;
        }

        // 匹配过程,i = 1,j = 0 开始,i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话,先让 j++,结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功,直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }
}


上一篇:在 Mac 上使用 `sed` 命令的几个坑


下一篇:902. 最短编辑距离