10. Regular Expression Matching
Problem's Link
----------------------------------------------------------------------------
Mean:
给定一个串s和一个自动机p（模糊字符只含有'.'和'*'），问串s是否能够和自动机p匹配.
analyse:
由于模糊字符只含有'.'和'*'，可不构造自动机.
直接用动态规划来做即可.
Time complexity: O(N)
view code
class Solution
{
public:
bool isMatch(string s, string p)
{
if(p.empty())
return s.empty();
if(p[1]=='*')
return isMatch(s,p.substr(2))
|| (!s.empty() && (s[0]==p[0] || '.'==p[0]) && isMatch(s.substr(1),p));
else
return !s.empty() && (s[0]==p[0] || '.' == p[0]) && isMatch(s.substr(1),p.substr(1));
}
};
{
public:
bool isMatch(string s, string p)
{
if(p.empty())
return s.empty();
if(p[1]=='*')
return isMatch(s,p.substr(2))
|| (!s.empty() && (s[0]==p[0] || '.'==p[0]) && isMatch(s.substr(1),p));
else
return !s.empty() && (s[0]==p[0] || '.' == p[0]) && isMatch(s.substr(1),p.substr(1));
}
};