| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
Easy |
|
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "sadbutsad", needle = "sad" Output: 0 Explanation: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto" Output: -1 Explanation: "leeto" did not occur in "leetcode", so we return -1.
Constraints:
1 <= haystack.length, needle.length <= 104haystackandneedleconsist of only lowercase English characters.
We compare the string needle with each character of the string haystack as the starting point. If we find a matching index, we return it directly.
Assuming the length of the string haystack is needle is
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i : i + m] == needle:
return i
return -1class Solution {
public int strStr(String haystack, String needle) {
if ("".equals(needle)) {
return 0;
}
int len1 = haystack.length();
int len2 = needle.length();
int p = 0;
int q = 0;
while (p < len1) {
if (haystack.charAt(p) == needle.charAt(q)) {
if (len2 == 1) {
return p;
}
++p;
++q;
} else {
p -= q - 1;
q = 0;
}
if (q == len2) {
return p - q;
}
}
return -1;
}
}class Solution {
private:
vector<int> Next(string str) {
vector<int> n(str.length());
n[0] = -1;
int i = 0, pre = -1;
int len = str.length();
while (i < len) {
while (pre >= 0 && str[i] != str[pre])
pre = n[pre];
++i, ++pre;
if (i >= len)
break;
if (str[i] == str[pre])
n[i] = n[pre];
else
n[i] = pre;
}
return n;
}
public:
int strStr(string haystack, string needle) {
if (0 == needle.length())
return 0;
vector<int> n(Next(needle));
int len = haystack.length() - needle.length() + 1;
for (int i = 0; i < len; ++i) {
int j = 0, k = i;
while (j < needle.length() && k < haystack.length()) {
if (haystack[k] != needle[j]) {
if (n[j] >= 0) {
j = n[j];
continue;
} else
break;
}
++k, ++j;
}
if (j >= needle.length())
return k - j;
}
return -1;
}
};func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
for i := 0; i <= n-m; i++ {
if haystack[i:i+m] == needle {
return i
}
}
return -1
}function strStr(haystack: string, needle: string): number {
const m = haystack.length;
const n = needle.length;
for (let i = 0; i <= m - n; i++) {
let isEqual = true;
for (let j = 0; j < n; j++) {
if (haystack[i + j] !== needle[j]) {
isEqual = false;
break;
}
}
if (isEqual) {
return i;
}
}
return -1;
}impl Solution {
pub fn str_str(haystack: String, needle: String) -> i32 {
let haystack = haystack.as_bytes();
let needle = needle.as_bytes();
let m = haystack.len();
let n = needle.len();
let mut next = vec![0; n];
let mut j = 0;
for i in 1..n {
while j > 0 && needle[i] != needle[j] {
j = next[j - 1];
}
if needle[i] == needle[j] {
j += 1;
}
next[i] = j;
}
j = 0;
for i in 0..m {
while j > 0 && haystack[i] != needle[j] {
j = next[j - 1];
}
if haystack[i] == needle[j] {
j += 1;
}
if j == n {
return (i - n + 1) as i32;
}
}
-1
}
}/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle) {
const slen = haystack.length;
const plen = needle.length;
if (slen == plen) {
return haystack == needle ? 0 : -1;
}
for (let i = 0; i <= slen - plen; i++) {
let j;
for (j = 0; j < plen; j++) {
if (haystack[i + j] != needle[j]) {
break;
}
}
if (j == plen) return i;
}
return -1;
};public class Solution {
public int StrStr(string haystack, string needle) {
for (var i = 0; i < haystack.Length - needle.Length + 1; ++i)
{
var j = 0;
for (; j < needle.Length; ++j)
{
if (haystack[i + j] != needle[j]) break;
}
if (j == needle.Length) return i;
}
return -1;
}
}class Solution {
/**
* @param String $haystack
* @param String $needle
* @return Integer
*/
function strStr($haystack, $needle) {
$strNew = str_replace($needle, '+', $haystack);
$cnt = substr_count($strNew, '+');
if ($cnt > 0) {
for ($i = 0; $i < strlen($strNew); $i++) {
if ($strNew[$i] == '+') {
return $i;
}
}
} else {
return -1;
}
}
}The Rabin-Karp algorithm essentially uses a sliding window combined with a hash function to compare the hashes of fixed-length strings, which can reduce the time complexity of comparing whether two strings are the same to
Assuming the length of the string haystack is needle is
func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
multi := 1
for i := 0; i < m; i++ {
target = (target*256%mod + int(needle[i])) % mod
}
for i := 1; i < m; i++ {
multi = multi * 256 % mod
}
for ; right < n; right++ {
sha = (sha*256%mod + int(haystack[right])) % mod
if right-left+1 < m {
continue
}
// 此时 left~right 的长度已经为 needle 的长度 m 了，只需要比对 sha 值与 target 是否一致即可
// 为避免 hash 冲突，还需要确保 haystack[left:right+1] 与 needle 相同
if sha == target && haystack[left:right+1] == needle {
return left
}
// 未匹配成功，left 右移一位
sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
left++
}
return -1
}function strStr(haystack: string, needle: string): number {
const m = haystack.length;
const n = needle.length;
const next = new Array(n).fill(0);
let j = 0;
for (let i = 1; i < n; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next[i] = j;
}
j = 0;
for (let i = 0; i < m; i++) {
while (j > 0 && haystack[i] !== needle[j]) {
j = next[j - 1];
}
if (haystack[i] === needle[j]) {
j++;
}
if (j === n) {
return i - n + 1;
}
}
return -1;
}Assuming the length of the string haystack is needle is