本文主要是介绍LeetCode - 10. Regular Expression Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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));
}
};
这篇关于LeetCode - 10. Regular Expression Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
