Dynamic programming C++


  • 0
    T
    class Solution {
    private:
        bool isMatchChar(char a, char b)
        {
            if(a == b)
                return true;
            else if(b == '?')
                return true;
            else
                return false;
        }
        
    public:
        bool isMatch(string s, string p) {
            int n, n2;
            int i, i2;
            n = s.length();
            n2 = p.length();
            vector<bool> DP;
            // We apply the dynamic programming to solve this problem
            DP.push_back(1);
            for(i=0; i<n; i++)
                DP.push_back(0);
            
            for(i2=0; i2<n2; i2++)
            {
                if(p.at(i2) != '*')
                {
                    for(i=0; i<n; i++)
                        DP[n-i] = DP[n-i-1] && isMatchChar(s.at(n-i-1), p.at(i2));
                    DP[0] = 0;
                }
                else
                {
                    for(i=0; i<n; i++)
                        DP[i+1] = DP[i+1] || DP[i];
                }
            }
            return DP[n];
        }
    };

Log in to reply
 

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