Open azl397985856 opened 1 year ago
class Solution {
func strStr(_ haystack: String, _ needle: String) -> Int {
let lenA = haystack.count
let lenB = needle.count
if lenB == 0 {
return 0
}
if lenB > lenA {
return -1
}
let endIndex = haystack.index(haystack.endIndex, offsetBy: -(lenB - 1))
for i in 0...(lenA - lenB) {
let startIndex = haystack.index(haystack.startIndex, offsetBy: i)
let endIndex = haystack.index(startIndex, offsetBy: lenB)
let substring = haystack[startIndex..<endIndex]
if substring == needle {
return i
}
}
return -1
}
}
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
if not haystack or len(haystack) < len(needle):
return -1
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i+len(needle)] == needle:
return i
return -1
暴力法时间复杂度m*n,滚动哈希选的好,直接是m+n
#暴力法和滚动哈希
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
tar=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
tar=tar*26+(ord(needle[i])-ord("a"))
tar%=prime
else:
hash_val = (hash_val - (ord(haystack[i - len(needle)]) - ord("a")) * ((26 ** (len(needle) - 1)) % prime)) * 26 + (ord(haystack[i]) - ord("a"))#更新哈希表的值,减去左边,加上右边
hash_val%=prime
if i>=len(needle)-1 and hash_val==tar and haystack[i-len(needle)+1:i+1]==needle:
return i-len(needle)+1
return 0 if hash_val==tar and haystack[i-len(needle)+1:i+1]==needle else -1
复杂度分析
class Solution {
public int strStr(String ss, String pp) {
int n = ss.length(), m = pp.length();
char[] s = ss.toCharArray(), p = pp.toCharArray();
// 枚举原串的「发起点」
for (int i = 0; i <= n - m; i++) {
// 从原串的「发起点」和匹配串的「首位」开始,尝试匹配
int a = i, b = 0;
while (b < m && s[a] == p[b]) {
a++;
b++;
}
// 如果能够完全匹配,返回原串的「发起点」下标
if (b == m) return i;
}
return -1;
}
}
class Solution { public int strStr(String ss, String pp) { int n = ss.length(), m = pp.length(); char[] s = ss.toCharArray(), p = pp.toCharArray(); // 枚举原串的「发起点」 for (int i = 0; i <= n - m; i++) { // 从原串的「发起点」和匹配串的「首位」开始,尝试匹配 int a = i, b = 0; while (b < m && s[a] == p[b]) { a++; b++; } // 如果能够完全匹配,返回原串的「发起点」下标 if (b == m) return i; } return -1; } }
class Solution:
def strStr(self, s: str, t: str) -> int:
def prefix_function(s):
n = len(s)
pi = [0] * n
j = 0
for i in range(1, n):
while j>0 and s[i] != s[j]:
j = pi[j-1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
n, m = len(s), len(t)
pi = prefix_function(t)
j = 0
for i in range(n):
while j>0 and s[i] != t[j]:
j = pi[j-1]
if s[i] == t[j]:
j += 1
if j == m:
return i-m+1
return -1
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle)
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
# Func: 计算偏移表
def calShiftMat(st):
dic = {}
for i in range(len(st)-1,-1,-1):
if not dic.get(st[i]):
dic[st[i]] = len(st)-i
dic["ot"] = len(st)+1
return dic
# 其他情况判断
if len(needle) > len(haystack):return -1
if needle=="": return 0
# 偏移表预处理
dic = calShiftMat(needle)
idx = 0
while idx+len(needle) <= len(haystack):
# 待匹配字符串
str_cut = haystack[idx:idx+len(needle)]
# 判断是否匹配
if str_cut==needle:
return idx
else:
# 边界处理
if idx+len(needle) >= len(haystack):
return -1
# 不匹配情况下,根据下一个字符的偏移,移动idx
cur_c = haystack[idx+len(needle)]
if dic.get(cur_c):
idx += dic[cur_c]
else:
idx += dic["ot"]
return -1 if idx+len(needle) >= len(haystack) else idx
28 实现 strStr(
入选理由
暂无
题目地址
[ 之 BF&RK 篇)
https://leetcode-cn.com/problems/implement-strstr/]( 之 BF&RK 篇)
https://leetcode-cn.com/problems/implement-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() 定义相符。