首页 > 代码库 > leetcode -10. Regular Expression Matching
leetcode -10. Regular Expression Matching
三种情况:
“a” 对应"a",
"." 对应 "a"
"a*" 对应 “aa”
当p为空,s为空时可以匹配;
若p的第二个字符为*,第一情况为不匹配(b, a*b);从 (b,b)开始匹配
第二种情况为匹配(a, a*); 首元素相同, 从( ,a*)开始匹配
若p的第二个字符不为*, 首字符必须要匹配, 再对首字符后的字符串匹配
recursive solution:
class Solution { public: bool isMatch(string s, string p) { if(p.empty()) return s.empty(); // if(s.empty()) return p.empty(); if(p[1]==‘*‘) { return (isMatch(s,p.substr(2))||((p[0]==s[0]||p[0]==‘.‘)&&!s.empty()&&isMatch(s.substr(1),p))); // if(p[0]==s[0]||p[0]==‘.‘&&!s.empty()) // return isMatch(s.substr(1),p); // else // return isMatch(s,p.substr(2)); } else { if(p[0]==s[0]||p[0]==‘.‘&&!s.empty()) return isMatch(s.substr(1),p.substr(1)); else return false; //return (p[0]==s[0]||p[0]==‘.‘)&&!s.empty()&&isMatch(s.substr(1),p.substr(1)); } } };
DP solution:
定义如果 dp[i+1][j+1]匹配,当s[0-i]与p[0-j]匹配。
如果 p[j]!=‘*‘, dp[i][j]=dp[i-1][j-1] && s[i-1]==p[j-1];
如果p[j]==‘*‘, dp[i][j]==dp[i][j-2], 0times repeat
dp[i][j]==dp[i-1][j]&& (s[i - 1] == p[j - 2] || p[j - 2] == ‘.‘)the pattern repeats for at least 1 times.
leetcode -10. Regular Expression Matching
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。