C++ code non-recursive 16ms


  • 1
    S

    These codes look not good but already accepted. any improvement space?

    class Solution {
    public:
    
        bool isMatch(string s, string p) {
            int i = 0, j = 0;
            int sAnchor = -1, pAnchor = -1;
    
            while(i < s.length() && j < p.length())
            {
                if(p[j] == '*')
                {
                    pAnchor = j;
                    // look for the next non-'*' char
                    j++;
                    bool hasQ = false;
                    while(j < p.length())
                    {
                        if(p[j] == '*')
                            j++;
                        else if(p[j] == '?')
                        {
                            if(!hasQ) sAnchor = i;
                            hasQ = true;
                            i++; j++;
                        }
                        else break; // get a non-'*'&'?' char
                    }
                    if(i > s.length()) return false;
                    if(j == p.length()) return true;
                    
                    while(i < s.length())
                    {
                        if(s[i] == p[j])
                        {
                            if (!hasQ) sAnchor = i;
                            i++; j++;
                            break;
                        }
                        else
                        {
                            i++;
                        }
                    }
                }
                
                else if(p[j] != '?')
                {
                    if(s[i] != p[j])
                    {
                        if(pAnchor >= 0)
                        {
                            i = sAnchor; sAnchor = -1;
                            j = pAnchor; pAnchor = -1;
                            i++;
                        }
                        else return false;
                    }
                    else // (s[i] == p[j])
                    {
                        i++; j++;
                    }
                }
                
                else // p[j] == '?'
                {
                    i++; j++;
                }
                
                if(i < s.length() && j == p.length())
                    if(pAnchor >= 0)
                    {
                        i = sAnchor; sAnchor = -1;
                        j = pAnchor; pAnchor = -1;
                        i++;
                    }
            }
    
            if(i == s.length())
            {
                while (j < p.length() && p[j] == '*')
                    j++;
                return j == p.length();
            }
    
            return false;
        }
    };

Log in to reply
 

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