【Day 83 】2021-12-01 - 28 实现 strStr( #102
Comments
思路:本题要求返回第2个串p在第1个串中第一次出现的位置, 如果不存在就返回-1。 KMP应该是这个题的最佳解法, 可以粗略地看成dp, 这样就很容易理解了。 方法: KMP算法先在原串和模式串地开头插入一个字符(比如: #), 方便后面更新next数组的值。 next数组的含义: next[i]: 字符串s的前缀串(s[1:i])与后缀串(s[j:len-1])相等时的最大长度len。 代码:实现语言: C++ class Solution {
public:
int strStr(string s, string p) {
if (p.empty())
return 0;
int n = s.size(), m = p.size();
s = '#' + s, p = '#' + p;
int next[m + 1]; /* 数组元素next[i]含义: 字符串s的前缀串(s[1:j])与后缀串(s[k:len-1])相等时的最大长度len */
memset(next, 0, sizeof(next));
for (int i = 2, j = 0; i <= m; i++) /* 更新next数组 */
{
while (j != 0 && p[i] != p[j + 1])
j = next[j];
if (p[i] == p[j + 1])
j++;
next[i] = j;
}
// 匹配一下
for (int i = 1, j = 0; i <= n; i++)
{
while (j != 0 && s[i] != p[j + 1])
j = next[j];
if (s[i] == p[j + 1])
j++;
if (j == m)
return i - m;
}
return -1;
}
};复杂度分析:
|
class Solution {
public int strStr(String haystack, String needle) {
int lenHaystack = haystack.length();
int lenNeedle = needle.length();
// needle equal to zero
if(needle.length() == 0){
return 0;
}
// haystack shorter than
if(lenNeedle < lenNeedle){
return -1;
}
for(int i = 0; i < lenHaystack - lenNeedle + 1; i++){
for(int j =0; j < lenNeedle; j++){
if(haystack.charAt(i+j) != needle.charAt(j)){
break;
}
}
}
}
} |
Note
Solutionclass Solution:
def strStr(self, haystack: str, needle: str) -> int:
len_h, len_n = len(haystack), len(needle)
if len_n == 0: return 0
if len_h < len_n: return -1
for i in range(len_h - len_n + 1):
if haystack[i:i + len_n] == needle:
return i
return -1Time complexity: O(NM) Space complexity: O(M) slicing creates a new string |
|
|
思路dbq 先这样 我有罪 代码class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not len(needle):
return 0
try:
return haystack.index(needle)
except Exception:
pass
return -1 |
|
思路: 复杂度分析:
代码(C++): class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.length();
int n = needle.length();
if (m < n) return -1;
if (n == 0) return 0;
int i = 0, j = 0, left = 0;
while (i < m && j < n) {
if (haystack[i] == needle[j]) {
++i;
++j;
} else {
left++;
i = left;
j = 0;
}
}
if (j == n) return left;
return -1;
}
}; |
link:https://leetcode.com/problems/implement-strstr/ 代码 Javascriptconst strStr = function (haystack, needle) {
if (haystack === needle || needle === '') {
return 0;
}
for (let i = 0; i < haystack.length; i++) {
if (haystack[i] === needle[0]) {
let temp = haystack.substring(i, i + needle.length);
if (temp === needle) {
return i;
}
}
}
return -1;
}; |
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not len(needle):
return 0
try:
return haystack.index(needle)
except Exception:
pass
return -1 |
|
偷个懒 - - class Solution:
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
lenA, lenB = len(haystack), len(needle)
if not lenB:
return 0
if lenB > lenA:
return -1
for i in range(lenA - lenB + 1):
if haystack[i:i + lenB] == needle:
return i
return -1 |
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle: return 0
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i+len(needle)] == needle:
return i
return -1 |
Idea:KMP Code:class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
if not haystack:
return -1 if needle else 0
p_needle = self.pStr(needle)
i, j = 0, 0
while i < len(haystack):
if j < len(needle) and haystack[i] == needle[j]:
j += 1
else:
if j == len(needle):
return i - j
while j > 0 and haystack[i] != needle[j]:
j = p_needle[j-1]
j += int(haystack[i] == needle[j])
i += 1
return i - j if j == len(needle) else -1
def pStr(self, pattern):
n = len(pattern)
if n < 2:
return [0]
dp = [0]*n
i, j =1, 0
while i < len(pattern):
if pattern[i] == pattern[j]:
dp[i] = j + 1
j += 1
else:
while pattern[i] != pattern[j] and j > 0:
j = dp[j-1]
j += int(pattern[i] == pattern[j])
dp[i] = j
i += 1
return dpComplexity:Time: O(M +N). M: length of pattern. N: length of string. |
思路
关键点代码
C++ Code: class Solution {
public:
int strStr(string haystack, string needle) {
// kmp method.
// calculate prefix.
if(haystack.size()< needle.size())
return -1;
vector<int> prefix(needle.size(), 0);
int left =0;
int right =1;
// sliding windows.
while(right < needle.size())
{
while(left>0 && needle[left] != needle[right])
{
left = prefix[left-1];
}
if(needle[left]==needle[right])
left ++;
prefix[right] = left;
right++;
}
left =0;
right =0;
while(left < haystack.size() && right < needle.size())
{
while(right>0 && haystack[left] != needle[right] )
{
right = prefix[right-1];
}
if(haystack[left] == needle[right] )
right++;
left++;
}
if(right == needle.size())
{
return left - right;
}
else
return -1;
}
};
|
|
BF class Solution(object):
def strStr(self, haystack, needle):
len1, len2 = len(haystack), len(needle)
if len2 == 0:
return 0
if len1 < len2:
return -1
for i in range(len1 - len2 + 1):
if haystack[i:(i + len2)] == needle:
return i
return -1 |
思路暴力查找 代码class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.isEmpty()) {
return 0;
}
int m = haystack.length();
int n = needle.length();
if (m < n) {
return -1;
}
for (int i=0; i<=m-n; i++) {
String subStr = haystack.substring(i, i + n);
if (subStr.equals(needle)) {
return i;
}
}
return -1;
}
}
|
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
if not haystack:
return -1
if len(needle) > len(haystack):
return -1
m, n = len(haystack), len(needle)
# 这个地方举个例子
for i in range(m - n + 1):
j = 0
while j < n:
if haystack[i + j] != needle[j]:
break
j += 1
if j == n:
return i
return -1 |
28. Implement strStr()https://leetcode.com/problems/implement-strstr/ Topics-slide window 思路slide window 代码 Pythonclass Solution:
def strStr(self, haystack: str, needle: str) -> int:
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i+len(needle)] == needle:
return i
return -1
复杂度分析时间复杂度： O(N*M) |
思路暴力。 代码(C++)class Solution {
public:
int strStr(string haystack, string needle) {
if (haystack.length() < needle.length()) {
return -1;
}
else {
for (int i=0; i<haystack.length()-needle.length()+1; i++) {
if (haystack.substr(i, needle.length()) == needle) return i;
}
return -1;
}
}
};复杂度分析
|
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0){
return 0;
}else{
for (int index=0; index<=haystack.length()-needle.length(); index++){
if (haystack.substring(index, index+needle.length()).equals(needle)){
return index;
}
}
}
return -1;
}
}var strStr = function(haystack, needle) {
if (needle.length==0){return 0};
for (let index=0; index<=haystack.length-needle.length; index++){
if (haystack.slice(index, index+needle.length) === needle){
return index;
};
};
return -1;
}; |
thoughtsKMP codeclass Solution:
def strStr(self, haystack: str, needle: str) -> int:
if haystack and needle:
def compute_next(needle):
next_list = [-1]
i, j = 0, -1
while i < len(needle):
if j == -1 or needle[i] == needle[j]:
i += 1
j += 1
next_list.append(j)
else:
j = next_list[j]
return next_list
next_list = compute_next(needle)
i = j = 0
while i < len(haystack) and j < len(needle):
if j == -1 or haystack[i] == needle[j]:
i += 1
j += 1
else:
j = next_list[j]
if j == len(needle):
return i - j
return -1 if needle else 0complexityTime O(m+n) Space O(1) |
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle == "": return 0
try:
return haystack.index(needle)
except ValueError:
return -1 |
|
思路 实现语言: C++
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.length();
int n = needle.length();
if (m < n) return -1;
if (n == 0) return 0;
int i = 0, j = 0, left = 0;
while (i < m && j < n) {
if (haystack[i] == needle[j]) {
++i;
++j;
} else {
left++;
i = left;
j = 0;
}
}
if (j == n) return left;
return -1;
}
};复杂度分析 |
思路滚动哈希 代码Python3 Code class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not haystack and not needle:
return 0
if not haystack or len(haystack) < len(needle):
return -1
if not needle:
return 0
hash_val = 0
target = 0
prime = 101
for i in range(len(haystack)):
if i < len(needle):
hash_val = hash_val * 26 + (ord(haystack[i]) - ord("a"))
hash_val %= prime
target = target * 26 + (ord(needle[i]) - ord("a"))
else:
hash_val = (
hash_val - (ord(haystack[i - len(needle)]) - ord("a")) * 26 ** (len(needle) - 1)
) * 26 + (ord(haystack[i]) - ord("a"))
hash_val %= prime
if i >= len(needle) - 1 and hash_val == target:
return i - len(needle) + 1
return 0 if hash_val == target else -1复杂度 设：待匹配串长为NN，模式串串长为MM
|
代码class Solution:
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
lenA, lenB = len(haystack), len(needle)
if not lenB:
return 0
if lenB > lenA:
return -1
for i in range(lenA - lenB + 1):
if haystack[i:i + lenB] == needle:
return i
return -1 |
var strStr = function(haystack, needle) {
if(needle=="") return 0;
//循环haystack，拿到每一项
for(let i=0;i<haystack.length;i++){
//判断haystack和needle首位相等的地方,那么从此刻的位置开始循环判断haystack和needle是否完全相等
if(haystack[i]==needle[0]){
let count=0;
//遍历needle
for(let j=0;j<needle.length;j++){
//每一次判断相等，都用count几下相等的次数，如果count的大小等于needle的长度，说明在haystack中存在完整的needle，即return 当前的i
if(haystack[j+i]==needle[j]){
count++;
if(count==needle.length){
return i;
}
}
}
}
}
return -1;
}; |
思路纯暴力匹配 代码/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
const lenA = haystack.length
const lenB = needle.length
if (lenB === 0) return 0
for (let i = 0; i < lenA; i ++) {
const curStr = haystack.slice(i, i + lenB)
if (curStr === needle) return i
}
return -1
};复杂度分析时间复杂度 O(M*N) [M,N 分别是两个字符串的长度] 空间复杂度 O(1) |
代码块var strStr = function (haystack, needle) {
let n = haystack.length;
let m = needle.length;
if (m === 0) return 0;
let next = new Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next[i] = j;
}
// 搞懂上面的，下面的也就懂了
for (let i = 0, j = 0; i < n; i++) {
// 如果当前i 和 j不一致，就回退到上一个相等的位置的下一个看看是否匹配
// 会不断回退，0为回退到边界，当回退到0意味着要重新从头开始匹配
while (j > 0 && haystack[i] !== needle[j]) {
j = next[j - 1];
}
if (haystack[i] === needle[j]) {
j++;
}
// 当j 和 m的长度相等时，就说明存在
if (j === m) {
return i - m + 1;
}
}
return -1;
};时间复杂度和空间复杂度
|
题目
代码复杂度Space: O(1) |
代码
C++ Code: class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) {
return 0;
}
int lenh = haystack.length();
int lenn = needle.length();
if (lenh < lenn) {
return -1;
}
for (int i = 0; i <= lenh - lenn; ++i) {
int j = 0;
while (j < lenn && haystack[i + j] == needle[j]) {
++j;
}
if (j == lenn) {
return i;
}
}
return -1;
}
};
复杂度分析 令 n 为数组长度。
|
思路
代码func strStr(haystack, needle string) int {
n, m := len(haystack), len(needle)
if m == 0 {
return 0
}
pi := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && needle[i] != needle[j] {
j = pi[j-1]
}
if needle[i] == needle[j] {
j++
}
pi[i] = j
}
for i, j := 0, 0; i < n; i++ {
for j > 0 && haystack[i] != needle[j] {
j = pi[j-1]
}
if haystack[i] == needle[j] {
j++
}
if j == m {
return i - m + 1
}
}
return -1
}复杂度
|
func strStr(haystack string, needle string) int {
return strings.Index(haystack, needle)
} |
|
|
class Solution { } |
思路brute force 代码int strStr(string haystack, string needle) {
if (needle.size() == 0) return 0;
if (haystack.size() < needle.size()) return -1;
for (int i = 0; i < haystack.size() - needle.size() + 1; ++i) {
if (haystack.substr(i, needle.size()) == needle) return i;
}
return -1;
}时间复杂度 O(N*M)空间复杂度 O(1) |
javaclass Solution {
public int strStr(String haystack, String needle) {
char[] haystackChar = haystack.toCharArray();
char[] needleChar = needle.toCharArray();
for(int i = 0;i + needleChar.length <= haystackChar.length;i++) {
boolean flag = true;
for(int j = 0;j < needleChar.length;j++) {
if(haystackChar[i + j] != needleChar[j]) {
flag = false;
break;
}
}
if(flag) return i;
}
return -1;
}
}复杂度
|
class Solution {
public int strStr(String haystack, String needle) {
int lenHaystack = haystack.length();
int lenNeedle = needle.length();
// needle equal to zero
if(needle.length() == 0){
return 0;
}
// haystack shorter than
if(lenNeedle < lenNeedle){
return -1;
}
for(int i = 0; i < lenHaystack - lenNeedle + 1; i++){
for(int j =0; j < lenNeedle; j++){
if(haystack.charAt(i+j) != needle.charAt(j)){
break;
}
}
}
}
} |
var strStr = function (haystack, needle) {
if (needle.length === 0)
return 0;
const getNext = (needle) => {
let next = [];
let j = -1;
next.push(j);
for (let i = 1; i < needle.length; ++i) {
while (j >= 0 && needle[i] !== needle[j + 1])
j = next[j];
if (needle[i] === needle[j + 1])
j++;
next.push(j);
}
return next;
}
let next = getNext(needle);
let j = -1;
for (let i = 0; i < haystack.length; ++i) {
while (j >= 0 && haystack[i] !== needle[j + 1])
j = next[j];
if (haystack[i] === needle[j + 1])
j++;
if (j === needle.length - 1)
return (i - needle.length + 1);
}
return -1;
}; |
【Day 83】28 实现 strStr()代码class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) {
return 0;
}
vector<int> pi(m);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] != needle[j]) {
j = pi[j - 1];
}
if (needle[i] == needle[j]) {
j++;
}
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = pi[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
};复杂度时间复杂度：O(N+M) 空间复杂度：O(M) |
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int i = 0; i + m <= n; ++i) {
bool flag = true;
for (int j = 0; j < m; ++j) {
if (haystack[i + j] != needle[j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
} |
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not len(needle):
return 0
try:
return haystack.index(needle)
except Exception:
pass
return -1 |
|
滑动窗口 /**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
let hLen = haystack.length, nLen = needle.length, res = -1;
if (hLen < nLen) return -1;
if (nLen === 0) return 0;
for(let i = 0; i < hLen - nLen + 1; i++) {
if (haystack.slice(i, i + nLen) === needle) {
res = i
break
}
}
return res;
}; |
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i + m <= n; i++) {
boolean flag = true;
for (int j = 0; j < m; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
} |
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) {
return 0;
}
int[] pi = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
j = pi[j - 1];
}
if (needle.charAt(i) == needle.charAt(j)) {
j++;
}
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = pi[j - 1];
}
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
} |
class Solution:
'''滚动hash'''
def strStr(self, haystack: str, needle: str) -> int:
lenH = len(haystack)
lenN = len(needle)
if not lenN:
return 0
if lenH < lenN:
return -1
target_hash = 0
hay_hash = 0
base = 101
for i in range(lenN):
target_hash = target_hash * 26 + (ord(needle[i])-ord('a'))
target_hash %= base
hay_hash = hay_hash * 26 + (ord(haystack[i])-ord('a'))
hay_hash %= base
if target_hash == hay_hash and haystack[:lenN] == needle:
return 0
for i in range(1, lenH-lenN+1):
hay_hash = (hay_hash - (ord(haystack[i-1]) -ord('a'))*(26**(lenN-1)))*26 + (ord(haystack[i+lenN-1]) -ord('a'))
hay_hash %= base
if hay_hash == target_hash and haystack[i:i+lenN] == needle:
return i
return -1*时间 O（m+n） |
代码
C++ Code: class Solution {
public:
vector<int> next;
void queryNext(string needle)
{
int n = needle.size();
int k = -1, j = 0;
next.assign(n,-1);
while(j<n-1)
{
if(k==-1||needle[j]==needle[k])
{
k++;
j++;
if(needle[j]==needle[k])
next[j] = next[k];
else
next[j] = k;
}
else
k = next[k];
}
}
int strStr(string haystack, string needle) {
queryNext(needle);
int i = 0, j = 0, hn = haystack.size(), nn = needle.size();
while(i<hn&&j<nn)
{
if(j==-1||haystack[i]==needle[j])
{
i++;
j++;
}
else
j = next[j];
}
if(j==nn)
return i - j;
return -1;
}
};
|
解题思路暴力解法。在haystack中找到substring，然后与needle比较。 代码class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.isEmpty()) {
return 0;
}
int m = haystack.length();
int n = needle.length();
if (m < n) {
return -1;
}
for (int i = 0; i <= m - n; i++) {
String subStr = haystack.substring(i, i + n);
if (subStr.equals(needle)) {
return i;
}
}
return -1;
}
}复杂度分析
|
28. 实现 strStr()实现 strStr() 函数。 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。 说明： 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 示例 1： 输入：haystack = "hello", needle = "ll" 输入：haystack = "aaaaa", needle = "bba" 输入：haystack = "", needle = "" 提示： 0 <= haystack.length, needle.length <= 5 * 104 思路一：KMP算法参考题解： 【宫水三叶】简单题学 KMP 算法 - 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com) 多图预警👊🏻详解 KMP 算法 - 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com) (4 封私信 / 60 条消息) 如何更好地理解和掌握 KMP 算法? - 知乎 (zhihu.com) 知乎的这个写的很好 代码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;
}
}复杂度分析时间复杂度：$O(m + n)$ 空间复杂度：$O(m)$ |
思路kmp 代码class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle)==0:
return 0
nexts=[0]*len(needle)
i=0
j=-1
nexts[0]=-1
while i<len(needle)-1:
if j==-1 or needle[i]==needle[j]:
i+=1
j+=1
nexts[i]=j
else:
j=nexts[j]
m=len(haystack)
n=len(needle)
i=0
j=0
while i<m and j<n:
if j==-1 or haystack[i]==needle[j]:
i+=1
j+=1
else:
j=nexts[j]
if j==n:
return i-j
else:
return -1 |
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i + m <= n; i++) {
boolean flag = true;
for (int j = 0; j < m; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
} |
Code:class Solution {
// =====Rabin-Karp=======to fina all the matches=======
public int strStr(String haystack, String needle) {
// edge cases
if (needle.length() == 0) {
return 0;
}
if (haystack.length() == 0 || needle.length() > haystack.length()) {
return -1;
}
int prime = 101;
int base = 26; // only lower-case English characters.
long initHaystackHash = getInitialHash(haystack, 0, needle.length() - 1, base, prime);
long initNeedleHash = getInitialHash(needle, 0, needle.length() - 1, base, prime);
for (int start = 0; start <= haystack.length() - needle.length(); start++) {
// for each start (except start == 0) recalculate the hash
// O(1)
if (start > 0) {
// recalculate hash by one step
// - leftmost
initHaystackHash -= haystack.charAt(start - 1);
// / base
initHaystackHash /= base;
// + new rightmost
// initHaystackHash += (haystack.charAt(start + needle.length() - 1) * Math.pow(base, needle.length() - 1) % prime) % prime;
// initHaystackHash %= prime;
initHaystackHash += haystack.charAt(start + needle.length() - 1) * Math.pow(base, needle.length() - 1);
}
if (initHaystackHash == initNeedleHash && haystack.substring(start, start + needle.length()).equals(needle)) {
return start;
}
}
return -1;
}
// % a prime to reduce the complexity
// "abc"
// 'a' + 'b' * base + 'c' * base * base
// inclusive
// O(needle) time complexity
private long getInitialHash(String str, int startIndex, int endIndex, int base, int prime) {
long hashRes = 0L;
for (int i = startIndex; i <= endIndex; i++) {
// hashRes += (str.charAt(i) * (Math.pow(base, i - startIndex) % prime)) % prime;
// hashRes %= prime;
hashRes += str.charAt(i) * (Math.pow(base, i - startIndex));
}
return hashRes;
}
public int strStr0(String haystack, String needle) {
// two edge cases
if (needle.length() == 0) {
return 0;
}
if (haystack.length() == 0 || needle.length() > haystack.length()) {
return -1;
}
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
int needleIndex = 0;
int haystackIndex = i;
while (haystack.charAt(haystackIndex) == needle.charAt(needleIndex)) {
needleIndex++;
haystackIndex++;
if (needleIndex == needle.length()) {
return haystackIndex - needle.length();
}
}
}
return -1;
}
// another way
public int strStr1(String haystack, String needle) {
// two edge cases
if (needle.length() == 0) {
return 0;
}
if (haystack.length() == 0 || needle.length() > haystack.length()) {
return -1;
}
// Logic: i is the starting index in haystack that potentially match the first char of needle
// j is the length of the matched needle part
// time complexity O(m * n), m is the length of haystack, n is the length of needle
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
for (int j = 0; j < needle.length() && haystack.charAt(i + j) == needle.charAt(j); j++) {
if (j == needle.length() - 1) return i;
}
}
return -1;
}
} |
|
class Solution: |
思路
代码javascript /*
* @lc app=leetcode.cn id=28 lang=javascript
*
* [28] 实现 strStr()
*/
// @lc code=start
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (needle === '') {
return 0
}
hLen = haystack.length
nLen = needle.length
for (let i = 0; i < hLen - nLen + 1; i++) {
if (haystack.slice(i, i + nLen) === needle) {
return i
}
}
return -1
};
// @lc code=end复杂度分析
|
思路BF，用RK由于大数类耗时多超时 代码import java.math.BigInteger;
class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
if (m == 0) {
return 0;
}
if (n < m) {
return -1;
}
for (int i = 0; i < n - m + 1; i++) {
int j = 0;
while (j < m) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
break;
}
j++;
}
if (j == m) {
return i;
}
}
return -1;
}
}复杂度time：O(n*m)，n是 |
class Solution {
public int strStr(String haystack, String needle) {
if(needle==null || needle.length()==0)
return 0;
int m = haystack.length();
int n = needle.length();
if(m<n)
return -1;
for(int i=0;i<=m-n;i++) {
if(haystack.substring(i,i+n).equals(needle))
return i;
}
return -1;
}
} |
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not haystack and not needle:
return 0
if not haystack or len(haystack) < len(needle):
return -1
if not needle:
return 0
hash_val = 0
target = 0
prime = 101
for i in range(len(haystack)):
if i < len(needle):
hash_val = hash_val * 26 + (ord(haystack[i]) - ord("a"))
target = target * 26 + (ord(needle[i]) - ord("a"))
else:
hash_val = (
hash_val - (ord(haystack[i - len(needle)]) - ord("a")) * 26 ** (len(needle) - 1)
) * 26 + (ord(haystack[i]) - ord("a"))
if i >= len(needle) - 1 and hash_val == target :
return i - len(needle) + 1
return -1 |
func strStr(haystack, needle string) int {
n, m := len(haystack), len(needle)
outer:
for i := 0; i+m <= n; i++ {
for j := range needle {
if haystack[i+j] != needle[j] {
continue outer
}
}
return i
}
return -1
}
|
|
Title:28. Implement strStr()Question Reference LeetCodeSolutionKMP Codeclass Solution {
public:
int strStr(string haystack, string needle) {
if (needle.length() == 0)
return 0;
vector<int> next(needle.length(), 0);
next[0] = -1;
// Generate next array
for (int i = 1; i < needle.length(); i++) {
int k = next[i - 1];
while (k != -1 && needle[i-1] != needle[k]){
k = next[k];
}
/*if (needle[i] == needle[k + 1])
next[i] = next[k + 1];
else */
next[i] = k + 1;
}
int i = 0;
int j = 0;
// Match the string
while (i < haystack.length() && j < (int) needle.length()) {
if (j == -1 || haystack[i] == needle[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == needle.length())
return i - needle.length();
return -1;
}
};
ComplexityTime Complexity and ExplanationO(m+n), m is the length of needle, o(m) is used to generate the next array; n is the length of haystack Space Complexity and ExplanationO(m), used to store the next array. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
28 实现 strStr(
入选理由
暂无
题目地址
[-BF&RK）
https://leetcode-cn.com/problems/implement-strstr/](-BF&RK）
https://leetcode-cn.com/problems/implement-strstr/)
前置知识
题目描述
The text was updated successfully, but these errors were encountered: