28 Implement strStr() 實現(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().

題目描述:
實現(xiàn) strStr() 函數(shù)。

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)。如果不存在，則返回 -1。

示例:

示例 1:

輸入: haystack = "hello", needle = "ll"
輸出: 2

示例 2:

輸入: haystack = "aaaaa", needle = "bba"
輸出: -1

說明:

當(dāng) needle 是空字符串時，我們應(yīng)當(dāng)返回什么值呢？這是一個在面試中很好的問題。

對于本題而言，當(dāng) needle 是空字符串時我們應(yīng)當(dāng)返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

思路:

1. 在每一個haystack字符上遍歷needle
   時間復(fù)雜度O(nm), 空間復(fù)雜度O(1), 其中n為haystack長度, m為needle長度
2. KMP算法
   時間復(fù)雜度O(n), 空間復(fù)雜度O(m), 其中n為haystack長度, m為needle長度
3. 當(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為字符串下標, j為最大前/后綴長度
        int i, j;
        // next數(shù)組初始一定為0, 即字符串第一個字符是沒有前/后綴的
        next[0] = 0;
        // 從第二個字符開始求取next數(shù)組
        for (i = 0, j = 1; j < len; j++) 
        {
            // 求取s[0]~s[j]相同的前/后綴長度
            /* 例子:
               "AB"
               前綴為["A"]
               后綴為["B"]
               無相同元素, 長度為0
               "ABCDAB"
               前綴為["A", "AB", "ABC", "ABCD", "ABCDA"]
               后綴為["BCDAB", "CDAB", "DAB", "AB", "B"]
               相同的元素為 "AB", 長度為2
            */
            /* i > 0, 是因為第一個字符是沒有前/后綴的
               而且查找失敗, i要退回next[i - 1]
            */
            /* 對于已經(jīng)求取的next[j] = i, 表示在字符串下標為 j處有長度為 i的前/后綴相等
               比如 A -> AB
               即 next[0] = 0
               對下次while循環(huán), 直接跳出
               ABCDA -> ABCDAB
               可以得到有一個前/后綴相等
               即next[4] = 1
               即
               ABCD A
                    |
                    A BCDA
               此時 next[4] = 1, j = 4, i = 1
               ABCD AB
                    ||
                    AB CDAB
               此時 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