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     }

 
原文地址:https://www.cnblogs.com/imyanzu/p/5163374.html