LeetCode LintCode C++ English Version substring easy brute force

Leetcode 28. Implement strStr()

Lintcode 13. Implement strStr()

Posted by Olivia Liu on August 14, 2019 | 阅读：次

Description

Implement strStr().

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

Answer

The main idea of this problem is to first find the entrance of substring in the haystack string and then determine if the rest of substring follows the entrance.

Code

C++

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.length();
        int m = needle.length();
        if(m == 0) return 0;
        if(m > n) return -1;
        for(int i = 0; i < n; ++i)
        {
            if(haystack[i] != needle[0]) continue;
            else if(n - i < m) return -1;
            for(int j = 0; j < m; ++j)
            {
                if(haystack[i + j] != needle[j]) break;
                else{
                    if(j == m - 1) return i;
                }
            }
        }
        return -1;
    }
};