Leetcode 28 - 实现 strStr(): 问题

Question

我在提交 Leetcode 28 时遇到了一个错误，这个错误至今没有解决。我的代码适用于大多数测试用例，但我对 haystack = "mississippi"、needle = "issip".

等场景感到困惑

我试过调试，发现整个 haystack 字符串都被遍历了，返回 -1 或未找到。它在每次出现 'i' 时找到的子字符串长度是 4, 1, 1.

int strStr(string haystack, string needle) {
        if (needle.empty()) {
            return 0;
        }
        if (haystack.empty() && !needle.empty()) {
            return -1;
        }
        int i = 0, j = 0, ans = 0;
        for (i; i < haystack.length(); i++) {
            if (haystack[i] == needle[0]) {
                j = 0;
                ans = i;
                for (j; j < needle.length(); j++) {
                    /*
                    if (haystack[i++] == needle[j]) {
                        continue;
                    }
                    else {
                        break;
                    }
                    */
                    if (haystack[i++] != needle[j]) {
                        break;
                    }
                }
                if (j == needle.length()) {
                    return ans;
                }
            }
            if (j == needle.length()) {
            return ans;
            }
        }
        return -1;
    }

输入："mississippi"、"issip" 输出：-1 (ans = 10, j = 1)

Answer 1

问题是你在

中修改了i

if (haystack[i++] != needle[j]) {

从而阻止探索第二个潜在匹配项。尝试

if (haystack[i + j] != needle[j]) {

并修复所有连锁问题。不过，我希望它能按原样工作。

Answer 2

该函数有几个缺点。

对于初学者来说，它应该被声明为

std::string::size_type strStr( const std::string &haystack, const std::string &needle );

并且如果在第一个字符串中找不到第二个字符串，则函数应该 return std::string::npos 与 class std::string 的所有类似成员函数一样。

函数参数shell是常量引用类型。

这个 if 语句中的条件

if (haystack.empty() && !needle.empty())

有一个多余的操作数。可以改写成

if (haystack.empty())

这个循环

for (i; i < haystack.length(); i++)

当第一个字符串尾部的大小小于第二个字符串的大小时应该停止迭代。

在这个 if 语句中

if (haystack[i++] != needle[j]) {

变量 i 递增，导致变量递增两次：一次在此语句中，第二次在循环中。

第二对这样的陈述

        if (j == needle.length()) {
        return ans;

是多余的。

函数可以按照演示程序中所示的方式编写。

#include <iostream>
#include <string>

std::string::size_type strStr( const std::string &haystack, const std::string &needle )
{
    if ( needle.empty() )
    {
        return 0;
    }
    else if ( haystack.empty() )
    {
        return -std::string::npos;
    }
    else
    {
        std::string::size_type ans = std::string::npos;

        auto n1 = haystack.length();
        auto n2 = needle.length();

        for ( std::string::size_type i = 0; ans == std::string::npos && i + n2 <= n1; i++ )
        {
            std::string::size_type j = 0;
            while ( j < n2 && haystack[i+j] == needle[j] ) j++;

            if ( j == n2 ) ans = i;
        }

        return ans;
    }
}

int main() 
{
    std::string haystack( "mississippi" );
    std::string needle( "issip" );

    std::cout << strStr( haystack, needle ) << '\n';

    return 0;
}

它的输出是

4

Leetcode 28 - 实现 strStr(): 问题

Leetcode 28 - Implement strStr(): question

c++

string

algorithm

function

strstr