10. Regular Expression Matching


此题为正则表达式匹配,只实现两个字符的匹配,'*'和'.'

'.' Matches any single character.
'*' Matches zero or more of the preceding element.
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

这里可以看到*只会出现在第二位之后的位置,.可以出现在任何位置代替任何单一字符
解题思路为一点一点切割掉*,递归匹配
 1     public boolean isMatch(String s, String p) {
 2         // 防止空指针
 3         if (p == null) {
 4             return s == null;
 5         }
 6         if (s == null) {
 7             return p == null;
 8         }
 9         int lenS = s.length();
10         int lenP = p.length();
11         // 都用p做判断是因为,要调用p.charAt防止数组下标溢出
12         if (lenP == 0) {
13             return lenS == 0;
14         }
15         // 如果lenP==1,要么ps相等,要么p=='.'
16         if (lenP == 1) {
17             if (p.equals(s) || (p.charAt(0) == '.' && lenS == 1)) {
18                 return true;
19             } else {
20                 return false;
21             }
22         }
23         // 上面已经写好了基本单元的判断,下面用递归,递归的条件是p的第二个字符是否为'*'
24         if (p.charAt(1) != '*') {
25             if (s.length() > 0 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) {
26                 return isMatch(s.substring(1), p.substring(1));
27             }
28             return false;
29         } else {
30             // 把*匹配的字符全部sub掉,在匹配剩下的
31             while (s.length() > 0 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) {
32                 if (isMatch(s, p.substring(2))) {
33                     return true;
34                 }
35                 s = s.substring(1);
36             }
37             // 当while条件不满足时,兜一下
38             return isMatch(s, p.substring(2));
39         }
40     }

优质内容筛选与推荐>>
1、JavaScript 字符串函数扩充
2、SQL注入的原理以及如何预防
3、GUI编程笔记(java)05:GUI事件监听机制原理和举例说明
4、phantomjs集成到scrapy中,并禁用图片,切换UA
5、Ubuntu Server 14.04 安装 LAMP


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号