Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/28.html
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 <= 104
haystack
andneedle
consist of only lowercase English characters.
Algorithm
To solve this problem, we need to make the following judgments:
- If the substring is empty, return 0
- If the length of the substring is greater than the length of the parent string, return -1.
Next, we will traverse the parent string. However, we don’t need to traverse the entire parent string. We can stop traversing when there are only len(parent_str) - len(substring) + 1
characters left. This can improve computational efficiency.
For each character in the parent string, we will traverse the substring again and compare the corresponding characters. If there is an unequal position in the corresponding position, we break out of the loop. If the substring is found, we return the starting position.
Code
-
public class Implement_strStr { public static void main(String[] args) { String a = "abc"; String b = "abc"; System.out.println(a == b); } public class Solution { // @para: h for haystack, n for needle public int strStr(String h, String n) { if(h == null || n == null || h.length() < n.length()) { return -1; } int window = n.length(); for(int i = 0; i + window - 1 < h.length(); i++) { if(h.substring(i, i + window).startsWith(n)) { return i; } } return -1; } } public class Solution_brute_force { // @para: h for haystack, n for needle public int strStr(String h, String n) { if(h == null || n == null || h.length() < n.length()) { return -1; } for(int i = 0; i < h.length(); i++) { if(h.substring(i).startsWith(n)) { return i; } } return -1; } } // ;p class Solution_ha { public int strStr(String haystack, String needle) { return haystack.indexOf(needle); } } } ############ class 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; } }
-
// OJ: https://leetcode.com/problems/implement-strstr/ // Time: O(MN) // Space: O(1) class Solution { public: int strStr(string haystack, string needle) { if (needle.size() > haystack.size()) return -1; for (int i = 0; i <= haystack.size() - needle.size(); ++i) { int j = 0; for (; j < needle.size() && haystack[i + j] == needle[j]; ++j); if (j == needle.size()) return i; } return -1; } };
-
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 -1 ############ class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ if len(haystack) == len(needle): if haystack == needle: return 0 else: return -1 for i in range(0, len(haystack)): k = i j = 0 while j < len(needle) and k < len(haystack) and haystack[k] == needle[j]: j += 1 k += 1 if j == len(needle): return i return -1 if needle else 0
-
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; 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; }
-
/** * @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; };
-
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; } } }
-
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; } }
-
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 } }