admin管理员组

文章数量:1636896

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack。

leetcode上面的一道题。就是一个字符串中是否存在子串和给定的另外一个字符串相等。如果相等，返回该子串首字母的索引。不存在就返回-1。

这道题最容易想到的就是暴力求解。即遍历haystack中的元素。如果某个元素和needle的首元素相等，那么接着比较needle的下一个元素。如果needle中的元素完全匹配，则返回。否则继续遍历haystack中的元素和needle首元素比较。相等，则重复上述过程，不等，继续往下走。代码如下：

int strStr(string haystack, string needle) {
        int length_h=haystack.size();
        int length_n=needle.size();
        if(length_n==0)
        {
            return 0;
        }
        if(length_h<length_n)
        {
            return -1;
        }
        int n=0;
        for(int i=0;i<length_h-length_n+1;i++)
        {
            if(haystack[i]==needle[n])
            {
                int j=1;
                for(;j<length_n;j++)
                {
                    if(haystack[i+j]!=needle[j])
                    {
                        break;
                    }
                }
                if(j==length_n)
                return i;
            }
        }
        return -1;
    }
这道题最经典的解法应该是KMP算法。

这里有一个关于KMP算法的比较通俗易懂的解释。链接如下：

http://wwwblogs/c-cloud/p/3224788.html。

本文标签： implementstrStrLeetCode

版权声明：本文标题：Implement strStr()--leetcode 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1729235295a1191922.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。