LeetCode_字符串_简单_28.实现strStr()
LeetCode 实现 简单 字符串 28 strstr
2023-09-27 14:25:46 时间
1.题目
实现 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 仅由小写英文字符组成
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-strstr
2.思路
本题显然属于字符串的模式匹配题,通常来说有BF(Btute-Force)算法(也称单匹配算法)和KMP算法这两种算法解题。
(1)BF算法
(2)KMP算法
3.代码实现
//思路1————BF算法
class Solution {
public int strStr(String haystack, String needle) {
if (needle == "") return 0;
int i = 0, j = 0;
//两个串都没有扫描完时循环
while (i < haystack.length() && j < needle.length()) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else {
//扫描目标串的i回退,子串从头开始匹配
i = i - j + 1;
j = 0;
}
}
//j超界,表示needle是haystack的子串
if (j >= needle.length()) {
return (i - needle.length());
} else {
return -1;
}
}
}
//思路2————KMP算法
class Solution {
public int strStr(String haystack, String needle) {
int next[] = new int[needle.length() + 1];
int i = 0, j = 0;
getNext(needle, next);
while (i < haystack.length() && j < needle.length()) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else {
//i不变,j后退
j = next[j];
}
}
if (j >= needle.length()) {
return i - needle.length();
} else {
return -1;
}
}
//由模式串needle求出next数组
public void getNext(String needle, int next[]) {
int j = 0, k = -1;
next[0] = -1;
while (j < needle.length()) {
if (k == -1 || needle.charAt(j) == needle.charAt(k)) {
j++;
k++;
next[j] = k;
} else {
k = next[k];
}
}
}
}
相关文章
- LeetCode每日一练 —— 225. 用队列实现栈
- 【LeetCode】字符串的排列 [M](滑动窗口)
- 【LeetCode】合并K个升序链表(使用优先级队列实现)
- LeetCode Letter Combinations of a Phone Number
- LeetCode 97 Interleaving String
- LeetCode_位运算_中等_318.最大单词长度乘积
- LeetCode_前缀树_中等_208.实现 Trie (前缀树)
- LeetCode_栈_简单_232.用栈实现队列
- LeetCode刷题(7)【栈&队列】用队列实现栈(C语言)
- LeetCode刷题(8)【栈&队列】用栈实现队列(C语言)
- LeetCode·每日一题·2351.第一个出现两次的字母·哈希
- LeetCode·每日一题·809.情感丰富的文字·双指针
- LeetCode·每日一题·856.括号的分数·栈模拟
- LeetCode·每日一题·1582.二进制矩阵中的特殊位置·模拟
- 【LeetCode从零单排】No 191.Number of 1 Bits(考察位运算)
- Leetcode-Pascal's Triangle
- LeetCode-454. 四数相加 II(Java实现)
- LeetCode-1370. 上升下降字符串(Java实现)
- LeetCode-67. 二进制求和(Golang实现)
- LeetCode-501. 二叉搜索树中的众数(Golang实现)
- LeetCode-35. 搜索插入位置(Golang实现)
- LeetCode-剑指 Offer 03. 数组中重复的数字(Goland实现)
- LeetCode-58. 最后一个单词的长度(Goland实现)
- LeetCode-169. 多数元素(Goland实现)
- LeetCode-104. 二叉树的最大深度(Goland实现)
- LeetCode-53. 最大子序和(Goland实现)
- [LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列
- [LeetCode] 697. Degree of an Array 数组的度
- [LeetCode] 289. Game of Life 生命游戏
- [LeetCode] 122. Best Time to Buy and Sell Stock II 买卖股票的最佳时间 II
- leetcode算法练习 JavaScript实现
- leetcode 84 柱状图中最大的矩形
- leetcode 28 找出字符串第一个匹配的下标(KMP实现strStr)