leetcode-28-Implement-strStr()

发表于   |  

描述

Implement strStr().

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

分析

题意是判断一个字符串是否有一个子串，如果有，返回 true，否则返回 false。暴力算法的话，复杂度是 $O(m*n)$。KMP 算法应该是解决这一问题的算法中最有名的了，不过这里暂时只给出最简单的暴力破解。

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        haystack_len = len(haystack)
        needle_len = len(needle)
    
        for i in range(haystack_len-needle_len+1):
            match = True
            for k in range(needle_len):
                if haystack[i+k] != needle[k]:
                    match = False
                    break
            if match is True:
                return i
        return -1

解决方案2(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.empty()) {
            return 0;
        }
        int haystack_len = haystack.size();
        int needle_len = needle.size();
        for (int i=0; i < haystack_len-needle_len+1; i++) {
            int j = 0;
            for (; j < needle_len; j++) {
                if (haystack[i+j] != needle[j]) {
                    break;
                }
            }
            if (j == needle_len) {
                return i;
            }
        }
        return -1;
    }
};

相关问题

(H) Shortest Palindrome (E) Repeated Substring Pattern

题目来源