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));
}
};
