10. Regular Expression Matching
----------------------------------------------------------------------------
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));
} };