[leetcode题解]28. Implement strStr()

Implement strStr().

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

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().

给定字符串和一个pattern,去找第一个出现该pattern的起始位置,如果没有就返回-1,如果存在该pattern,则返回第一次出现的起始下标。

比较好的方法应该是kmp,但是比较复杂,直接暴力解。

每个位置,往后搜,如果能匹配到pattern的尾部,说明存在,直接把头部下标返回即可。

C语言代码如下:

int strStr(char * haystack, char * needle){
    int hlen = strlen(haystack);
    int nlen = strlen(needle);
    int i, j;
    bool mark;
    
    if (nlen > hlen) {
        return -1;
    }
    
    for (i = 0; i <= hlen - nlen; i++) {
        mark = true;
        for (j = 0; j < nlen; j++) {
            if (haystack[i + j] != needle[j]) {
                mark = false;
                break;
            }
        }
        
        if (mark) {
            return i;
        }
    }
    
    return -1;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]28. Implement strStr()

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/216.html

相关文章