Simple and easy understanding c++ solution using backtracking and recursion

  • 0
    class Solution {
            int strStr(string haystack, string needle) {
                int hLen = haystack.size();
                int nLen = needle.size();
                if(nLen==0) return 0; // special treat
                for(int i=0; i<=hLen-nLen; i++) // for characters in haystack, we test if it matches from here
                    if(equal(haystack, i, needle, nLen, 0)) return i;
                return -1;
            bool equal(const string& haystack, int hPos,
                        const string& needle, const int nLen, int nPos)
                if(haystack[hPos] != needle[nPos]) return false;
                if(nPos == nLen-1) return true;
                return equal(haystack, hPos+1, needle, nLen, nPos+1);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.