28 Implement strStr() 實(shí)現(xiàn)strStr()
Description:
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example:
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
題目描述:
實(shí)現(xiàn) strStr() 函數(shù)。
給定一個(gè) haystack 字符串和一個(gè) needle 字符串唆阿，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)益涧。如果不存在，則返回 -1驯鳖。
示例:
示例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2
示例 2:
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
說明:
當(dāng) needle 是空字符串時(shí)闲询，我們應(yīng)當(dāng)返回什么值呢久免？這是一個(gè)在面試中很好的問題。
對(duì)于本題而言扭弧，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 阎姥。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。
思路:
- 在每一個(gè)haystack字符上遍歷needle
時(shí)間復(fù)雜度O(nm), 空間復(fù)雜度O(1), 其中n為haystack長(zhǎng)度, m為needle長(zhǎng)度 -
KMP算法
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(m), 其中n為haystack長(zhǎng)度, m為needle長(zhǎng)度 - 當(dāng)然最偷懶的算法是直接調(diào)用strstr()(C++)/indexOf()(Java)
代碼:
C++:
class Solution
{
private:
// 求next數(shù)組
void ComputePrefix(string s, int next[])
{
int len = s.length();
// i為字符串下標(biāo), j為最大前/后綴長(zhǎng)度
int i, j;
// next數(shù)組初始一定為0, 即字符串第一個(gè)字符是沒有前/后綴的
next[0] = 0;
// 從第二個(gè)字符開始求取next數(shù)組
for (i = 0, j = 1; j < len; j++)
{
// 求取s[0]~s[j]相同的前/后綴長(zhǎng)度
/* 例子:
"AB"
前綴為["A"]
后綴為["B"]
無相同元素, 長(zhǎng)度為0
"ABCDAB"
前綴為["A", "AB", "ABC", "ABCD", "ABCDA"]
后綴為["BCDAB", "CDAB", "DAB", "AB", "B"]
相同的元素為 "AB", 長(zhǎng)度為2
*/
/* i > 0, 是因?yàn)榈谝粋€(gè)字符是沒有前/后綴的
而且查找失敗, i要退回next[i - 1]
*/
/* 對(duì)于已經(jīng)求取的next[j] = i, 表示在字符串下標(biāo)為 j處有長(zhǎng)度為 i的前/后綴相等
比如 A -> AB
即 next[0] = 0
對(duì)下次while循環(huán), 直接跳出
ABCDA -> ABCDAB
可以得到有一個(gè)前/后綴相等
即next[4] = 1
即
ABCD A
|
A BCDA
此時(shí) next[4] = 1, j = 4, i = 1
ABCD AB
||
AB CDAB
此時(shí) next[5] = 2, j = 5, i = 2
*/
// 每次查找不匹配, i退回next[i - 1]
while (i > 0 and s[i] != s[j]) i = next[i - 1];
if (s[i] == s[j]) i++;
next[j] = i;
}
}
public:
int strStr(string haystack, string needle)
{
if (!needle.length()) return 0;
if (!haystack.length()) return -1;
int next[needle.length()];
ComputePrefix(needle, next);
int j = 0;
for (int i = 0; i < haystack.length(); i++)
{
// 每次查找不匹配, j退回next[j - 1]
while (j > 0 and needle[j] != haystack[i]) j = next[j - 1];
if (needle[j] == haystack[i]) j++;
if (j == needle.length()) return i - j + 1;
}
return -1;
}
};
Java:
class Solution {
public int strStr(String haystack, String needle) {
return haystack.indexOf(needle);
}
}
Python:
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
for i in range(len(haystack)):
j = i + len(needle)
if j <= len(haystack) and haystack[i:j] == needle:
return i
return -1
