hmm船公司网站,网站诊断示例,南通网站推广,网站建设的后期服务要包括什么软件LeetCode-10. 正则表达式匹配 问题分析算法描述程序代码CGo 问题分析
这道题的难点主要在于*号的匹配#xff0c;这里记dp[i][j]表示s[1...i]和p[1...j]能否完成匹配#xff0c;先根据特殊情况归纳总结#xff1a;
*号匹配 0 次#xff0c;则dp[i][j] dp[i][j-2]*号匹配… LeetCode-10. 正则表达式匹配 问题分析算法描述程序代码CGo 问题分析
这道题的难点主要在于*号的匹配这里记dp[i][j]表示s[1...i]和p[1...j]能否完成匹配先根据特殊情况归纳总结
*号匹配 0 次则dp[i][j] dp[i][j-2]*号匹配 1 次则dp[i][j] dp[i-1][j-2] s[i] p[j-1]*号匹配 2 次则dp[i][j] dp[i-2][j-2] s[i-1] p[j-1] s[i] p[j-1]*号匹配 3 次则dp[i][j] dp[i-3][j-2] ...*号匹配 k 次则dp[i][j] dp[i-k][j-2] ...
对上述进行归纳可得
当k 0时dp[i][j] dp[i][j-2]当k 1时将dp[i][j] dp[i][j-2]带入等式左边可得dp[i][j-2] dp[i-k][j-2] ...。因此最终化简可得dp[i][j] dp[i-1][j] s[i] p[j-1]
算法描述
状态定义dp[i][j]表示s[1...i]和p[1...j]能否完成匹配
状态转移 若p[j] *可能的状态转移如下
*表示匹配 0 个前面的那一个元素dp[i][j] dp[i][j-2]*表示匹配多个前面的那一个元素dp[i][j] (s[i] p[j-1] || p[j-1] .) dp[i-1][j] 若p[j] ! *则只能进行单元素的匹配dp[i][j] (s[i] p[j] || p[j] .) dp[i-1][j-1]
边界情况
dp[0][0] true子字符规律p[1...i]可能匹配空字符串sdp[0][i] p[i] * dp[0][i-2]
程序代码
C
class Solution {
public:bool isMatch(string s, string p) {int m s.size(), n p.size();s s;p p;vectorvectorbool dp(m 1, vectorbool(n 1, false));// 初始化dp[0][0] true;for(int i 2; i n; i) dp[0][i] p[i] * dp[0][i-2];for(int i 1; i m; i) {for(int j 1; j n; j) {if(p[j] *) {dp[i][j] dp[i][j-2] || (s[i] p[j-1] || p[j-1] .) dp[i-1][j];}else {dp[i][j] (s[i] p[j] || p[j] .) dp[i-1][j-1];}}}return dp[m][n];}
};Go
func isMatch(s string, p string) bool {m, n : len(s), len(p)s sp pdp : make([][]bool, m 1)for i : 0; i len(dp); i {dp[i] make([]bool, n 1)}// 初始化dp[0][0] truefor i : 2; i n; i {dp[0][i] dp[0][i-2] p[i] *}for i : 1; i m; i {for j : 1; j n; j {if p[j] * {dp[i][j] dp[i][j-2] || dp[i-1][j] (s[i] p[j-1] || p[j-1] .)} else {dp[i][j] dp[i-1][j-1] (s[i] p[j] || p[j] .)}}}return dp[m][n]
}
