题解 | #正则表达式匹配#

动态规划

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

class solution
{
public:
    int getResult(const string &str, const string &pattern)
    {
        int sLength = str.size(), pLength = pattern.size();
        vector<vector<int>> dp(sLength + 1, vector<int>(pLength + 1, 0));
        dp[0][0] = 1;
        
        for (int i = 0; i <= sLength; i++)
        {
            for (int j = 1; j <= pLength; j++)
            {
                if (pattern[j - 1] != '*')
                {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.');
                }
                else
                {
                    dp[i][j] = (j >= 2 && dp[i][j - 2]) || (i > 0 && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.') && dp[i - 1][j]);
                }
            }
        }
        
        return dp[sLength][pLength];
    }
    
};

int main()
{
    string str, pattern;
    getline(cin, str);
    getline(cin, pattern);
    
    solution mSolution;
    int ret = mSolution.getResult(str, pattern);
    if (ret)
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }
    
    return 0;
}