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


  • 0
    D
    class Solution {
        public:
            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.