leetcode 10、Regular Expression Matching

本题大意: 给你一个字符串s， 以一个模式串p，而模式串中规则匹配的只有 '.' 和 ‘*’，其中 ‘.’ 代表匹配任意一个字符，‘*’ 代表匹配的前一个字符有0个或多个，求字符串s和模式串p是否匹配?

题解：本题利用递归的思想使用模式串p去匹配字符串s；

1、当p为空的时候，s为空返回true，否则返回false

2、当p只有一个字符时，s 中的字符是否为1并且 （s[0] == p[0] or p[0] == '.'）;

3、当p[1] != '*'时， 判断s是否为空，是返回false， 否则返回（s[0] == p[0] or p[0] == '.'） && isMatch(s.substr(1), p.substr(1))

      substr(start) 表示截取从字符串start的位置到字符串的末尾

4、当p[1] == '*'时， 判断s是否为空 并且 （s[0] == p[0] or p[0] == '.'）; 当s和p.substr(2)匹配时直接返回true（由于*可以匹配的前一个字符可以是0个，所以如果s和p.substr(2)匹配，前面的可以认为是0个，是符合模式匹配串的），如果不匹配则s = s.substr(1)

5、返回isMatch（s, p.substr(2)）

 

#include <iostream> using namespace std;bool isMatch(string s, string p) {if (p.empty()) return s.empty();if (p.size() == 1){return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));}if (p[1] != '*'){if (s.empty()) return false;return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));}while (!s.empty() && (s[0] == p[0] || p[0] == '.')){if (isMatch(s, p.substr(2))) return true;s = s.substr(1);}return isMatch(s, p.substr(2)); }int main() {string s = "ab";string p = "a*";cout << isMatch(s, p) << endl; }

 

 

 

 

 

 

 

 

 

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的leetcode 10、Regular Expression Matching的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。