济宁网站建设哪家便宜,江门网站推广设计,俄罗斯网站后缀,自己搞个网站需要多少钱10. 正则表达式匹配#xff08;困难#xff09; 题解 如果从左向右进行匹配的话#xff0c;需要考虑字符后是否有 * 。 因此选择从右向左扫描更为简单。 *前面肯定有一个字符#xff0c;它像是一个拷贝器#xff0c;能够复制前面的单个字符#xff0c;甚至也可以把这个…10. 正则表达式匹配困难 题解 如果从左向右进行匹配的话需要考虑字符后是否有 * 。 因此选择从右向左扫描更为简单。 *前面肯定有一个字符它像是一个拷贝器能够复制前面的单个字符甚至也可以把这个字符消除出现 0 次。 两个字符串是否匹配取决于最右边的字符是否匹配以及剩余的子串是否匹配。其中「剩余的子串是否匹配」就是本道题的子问题。 状态定义定义 dp[i][j] 为第一个字符串到 i 为止第二个字符串到 j 为止两个字符串是否匹配。如果匹配dp[i][j] true如果不匹配dp[i][j] false。 子问题的考虑 情况一s[i-1] 和 p[j-1] 匹配即 s[i-1] p[j-1] || p[j-1] .。那么只需要考虑剩余的子串是否匹配即 dp[i][j] dp[i-1][j-1]; 情况二s[i-1] 和 p[j-1] 不匹配。这时候不能直接认为两个字符串不匹配而是需要进一步考虑 p[j-1] * 的情况。但是如果不是 * 那么肯定不匹配。 对于 * 它可以匹配 0 个或多个字符。当s[i-1] 和 p[j-2] 匹配且 p[j-1] ‘*’ 时需要考虑三种情况 * 使 dp[j-2] 出现 0 次、1 次或 2次。只要其中一种情况能使得两个子串匹配我们就可以继续考虑剩余子串是否匹配。状态转移方程为dp[i][j] dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j]; 当s[i-1] 和 p[j-2] 不匹配且 p[j-1] ‘*’ 时可以利用 * 消除不匹配字符 p[j-2]考虑 s[i-1] 和 p[j-3] 是否匹配。状态转移方程为dp[i][j] dp[i][j-2];。 初始情况当两个字符串都是空串的时候一定匹配因此 dp[0][0] true; 当 s 为空时如果 p 的右端字符是 * 那么就可以使得 p 也变成空串当 p 为空两个字符串一定不匹配。 代码 class Solution {
public:bool isMatch(string s, string p) {int m s.size(), n p.size();vectorvectorbool dp(m1, vectorbool(n1, false));// 两个空字符串一定匹配dp[0][0] true;// 如果s为空串 p[j-1]* 也能够匹配for(int j1; jn; j){if(p[j-1] *){dp[0][j] dp[0][j-2];}}// 从右向左匹配for(int i1; im; i){for(int j1; jn; j){// s[i-1]和p[j-1]匹配if(s[i-1] p[j-1] || p[j-1] .){dp[i][j] dp[i-1][j-1];}// s[i-1]和p[j-1]不匹配else{// p[j-1] * 且 s[i-1]和p[j-2]匹配if(p[j-1] *){dp[i][j] dp[i][j-2];if(s[i-1] p[j-2] || p[j-2] .){dp[i][j] dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];}}}}}return dp[m][n];}
};收获 理解错了 * 的意思* 类似于一个拷贝器 能匹配前一个元素也能消除前一个元素匹配零个。这道题需要考虑多种情况感觉很难想得这么全面。
