C++ 12 ms sub-string search solution (no backtracking)


  • 0
    V

    The idea is to split the pattern to sub-strings by '*', and then just check if we can sequentially find all these sub-strings in the string. While I think that this is simpler to understand than backtracking, handling edge cases adds some complexity to the code below.

    bool isMatch(string s, string p)
    {
        auto s_size = s.size(), p_size = p.size();
        auto s_start = 0, p_start = 0, subp_size = 0;
        
        if (p_size == 0) return s_size == 0;
    
        for (auto i = 0; i <= p_size; ++i)
        {
            if (i == p_size || p[i] == '*') // Checking the last sub-string in the same cycle.
            {
                if (subp_size > 0)
                {
                    if (s_size - s_start < subp_size) return false;
                    if (i == p_size && s_size - subp_size < s_start) return false;
                    if (i == p_size && p_start == 0 &&  subp_size != s_size) return false;
    
                    // When i == p_size, we should match the end of the string.
                    // When p_start == 0, we should match the beginning of the string.
                    auto found = string::npos;
                    for (auto k = (i == p_size ? s_size - subp_size : s_start); k < (p_start == 0 ? 1 : s_size - subp_size + 1); ++k)
                    {
                        auto j = 0;
                        for (; j < subp_size; ++j)
                        {
                            if (s[k + j] != p[p_start + j] && p[p_start + j] != '?')
                            {
                                break;
                            }
                        }
            
                        if (j == subp_size) 
                        {
                            found = k;
                            break;
                        }
                    }
    
                    if (found == string::npos) return false;
    
                    s_start = found + subp_size;
                    subp_size = 0;
                }
    
                p_start = i + 1;
            }
            else
            {
                ++subp_size;
            }
        }
        
        return true;
    }
    

Log in to reply
 

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