strStr()的实现

Question

返回大海捞针第一次出现的指数，或者-1如果针不是干草堆的一部分。当指针是空字符串时，我们将返回0。例1:输入: haystack = "hello"，needle = "ll“输出:2

这是我的密码：

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle == "") return 0;
        int i = 0, j = 0, poz = -1;
        if (needle.size() > haystack.size()) return -1;
        while (i < haystack.size() && j < needle.size()) {
            if (haystack[i] == needle[j]) {
                poz = i;
                while (i < haystack.size() && j < needle.size() && haystack[i] == needle[j]) {
                    i++;
                    j++;
                }
                if (j == needle.size()) return poz;
                else {
                    i = poz + 1;
                    j = 0;
                }
            } else i++;
        }
        return -1;
    }
};

但是对于包含两个字符串(5* 10^4字符)的测试用例，我得到了TLE。你能帮我改正我的密码吗？

Answer 1

2在你的蛮力解决方案的改进点。

不要每次都要找到干草堆和针头大小，而是在代码开始时只找到一次，将这两个值存储在两个变量中，然后使用那些遍历干草堆每个位置的variables.

• While，检查剩余的干草堆大小是否比指针小。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int needleSz = needle.size();
        int haystackSz = haystack.size();
        if (needleSz == 0) return 0;
        if (needleSz > haystackSz) return -1;
        int i = 0, j = 0, poz = -1;

        while (i < haystackSz) {
            if (haystackSz - i < needleSz) return -1;
            if (haystack[i] == needle[j]) {
                poz = i;
                while (i < haystackSz && j < needleSz && haystack[i] == needle[j]) {
                    i++;
                    j++;
                }
                if (j == needleSz) {
                    return poz;
                }
                else {
                    i = poz + 1;
                    j = 0;
                }
            } 
            else i++;
        }
        return -1;
    }
};