CY-Left

LeetCode基本功底

[leetcode]Implement strStr()

Implement strStr 实现 strstr() 方法

原题&翻译

Implement strStr().

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

返回在 haystack 中第一次匹配到 needle 字符串的位置。如果没有匹配到,返回 -1;

案例 1:

给出的 haystack 为 "hello", needle = "ll"
输出: 2

案例 2:

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

解题思路

傻瓜解法

两层 FOR

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hayLen = haystack.length();
        int needLen = needle.length();
        if (needLen == 0) return 0;
        if (hayLen == 0) return -1;

        for(int i=0;i<hayLen;i++){
            int j = 0;
            for(;j<needLen;j++){
                if(needle[j]!=haystack[i+j]) break;
            }
            if(j==needLen){return i;}
        }
        return -1;
    }
};

KMP

这里留个坑

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=680