class Solution {
public:
int strStr(string haystack, string needle) {
}
};
28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104haystack 和 needle 仅由小写英文字符组成原站题解
python3 解法, 执行用时: 32 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-18 15:25:14
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle: return 0
lnd = len(needle)
lnf = len(haystack)
if lnd > lnf: return -1
# 偏移表预处理
dic ={v:lnd-k for k,v in enumerate(needle)}
idx = 0
while idx+lnd <= lnf:
# 待匹配字符串
str_cut = haystack[idx:idx+lnd]
# 判断是否匹配
if str_cut == needle:
return idx
elif idx+lnd == lnf:
return -1
else:
# 不匹配情况下，根据下一个字符的偏移，移动idx
nextc = haystack[idx+lnd]
idx += dic[nextc] if dic.get(nextc) else lnd+1
return -1
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-18 15:23:04
// KMP算法
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
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-18 15:22:23
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
}
golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-18 15:21:17
func strStr(haystack string, needle string) int {
return strings.Index(haystack, needle)
}
python3 解法, 执行用时: 32 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-18 15:19:13
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle in haystack: return haystack.index(needle)
return -1
php 解法, 执行用时: 8 ms, 内存消耗: 18.7 MB, 提交时间: 2022-11-18 15:18:22
class Solution {
/**
* @param String $haystack
* @param String $needle
* @return Integer
*/
function strStr($haystack, $needle) {
$r = strpos($haystack, $needle);
if ( $r === false ) return -1;
return $r;
}
}
javascript 解法, 执行用时: 2008 ms, 内存消耗: N/A, 提交时间: 2018-08-29 15:48:28
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
return haystack.indexOf(needle);
};
golang 解法, 执行用时: 4 ms, 内存消耗: N/A, 提交时间: 2018-08-29 15:47:54
func strStr(haystack string, needle string) int {
return strings.Index(haystack, needle)
}
java 解法, 执行用时: 5 ms, 内存消耗: N/A, 提交时间: 2018-08-29 15:42:40
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: N/A, 提交时间: 2018-08-29 15:42:04
class Solution:
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if needle in haystack:
return haystack.index(needle)
return -1