C++ implementation of DP


  • 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 = s.length();
            vector<bool> DP;
            DP.push_back(1);
            int i;
            for(i=1; i<=n; i++)
                DP.push_back(0);
            int n2 = p.length();
            int i2;
            for(i2=0; i2<n2; i2++)
            {
                if(i2+1 < n2 && p[i2+1] == '*')
                {
                    for(i=0; i<n; i++)
                        if(DP[i] && isMatchChar(s.at(i), p.at(i2)))
                            DP[i+1] = 1;
                    i2++;
                }
                else
                {
                    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;
                }
            }
            return DP[n];
        }
    };

Log in to reply
 

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