力扣第十题C++正则表达式匹配

题目

知识点

正则表达式

字符匹配

regex

题解

动态规划

注意或等于|=

auto singleMatch(char c_s, char c_p) { if (c_s == '1') return false;//1和字符都不匹配 if (c_p == '.') return true;//.和任何字符都匹配 return c_s == c_p;//既不是1也不是.，直接返回两者比较后的结果 } bool isMatch(string s, string p) { s = '1' + s;//占位字符 p = '1' + p; int m = s.size(); int n = p.size(); //创建二维数组f，初始化都为false，f有m列，每列n个元素 vector<vector<int>> f(m, vector<int>(n, false)); f[0][0] = true; //按列填 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (p[j] == '*') { f[i][j] |= f[i][j - 2];//f[i][j] = f[i][j] || f[i][j - 2] if (singleMatch(s[i], p[j - 1])) { f[i][j] |= f[i - 1][j]; } } else { if ( singleMatch(s[i], p[j]) ) { f[i][j] |= f[i - 1][j - 1]; } } }//j }//i return f[m - 1][n - 1]; }