题目大意：
正则表达式匹配
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。 '*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。
示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入: s = "aa" p = "a*" 输出: true 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入: s = "aab" p = "c*a*b" 输出: true 解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入: s = "mississippi" p = "mis*is*p*." 输出: false
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=10
解题思路分析：
这道题是比较典型要使用递归思想或者是动态规划DP来思考的题目。题目的难点也是关键点在于对星号的匹配。按照题目来分析，星号是不会单独出现，他需要根据前一个字符来匹配1个，多个或者0个连续相同字符。因此我们从星号的判断入手分析，分为两种情况，第一种情况，当前字符之后一位如果不是星号，那么只匹配s和p的当前位置即可，例如
String s = "abc"; String p = "a.b"; // 当index等于0时，匹配成功 s.charAt(0) = 'a'; p.charAt(0) = 'a'; // 当index等于1时，由于'.'可以匹配任何字符，同样匹配成功 s.charAt(1) = 'b'; p.charAt(1) = '.'; // 当index等于2时，匹配失败 s.charAt(2) = 'c'; p.charAt(2) = 'b';
另外一种情况即是p当前位之后一位的字符为星号的情况，这是本题的关键，我们知道，当前字符与之后一位的星号组合起来的长度是在0到无穷大的范围，如果长度为0，也就是说可以无视掉p当前字符以及星号，那么，匹配字符p的当前index可以跳到index + 2, 而s的index不变，问题就变成了判断p.charAt(index + 2)是否等于s.charAt(index)。反之，如果p的当前字符与星号的组合长度大于等于1，就要首先判断p的当前字符是否等于s的当前字符，并且再看p.charAt(index)是否等于s.charAt(index + 1)。我们用递归方法简单的描述一下上面的逻辑。
public boolean isMatch(String s, String p, int sIndex, int pindex) {
char charP = p.charAt(pindex); // p当前字符
char charS = s.charAt(sIndex); // s当前字符
if (pindex + 1 < pLength && p.charAt(pindex + 1) == '*') {
return (charS == charP || charP == '.') && isMatch(s, p, sIndex + 1, pindex)
|| isMatch(s, p, sIndex, pindex + 2);
} else {
return (charS == charP || charP == '.') && isMatch(s, p, sIndex + 1, pindex + 1);
}
}当然，上面的代码只是一个简单的思路，并没有考虑charAt()方法越界的情况。在LeetCode提交之后顺利通过(AC)，不过执行速度稍微有些缓慢，只击败了60%的代码执行效率。仔细一分析，才恍然大悟，说好的动态规划呢？我们需要一个数组来记录下，对应sIndex和pindex的匹配结果，这样可以避免不必要的重复计算，最后是完整的逻辑代码。
int pLength = 0;
int sLength = 0;
Boolean[][] dp;
public boolean isMatch(String s, String p) {
pLength = p.length(); // 字符串p的长度
sLength = s.length(); // 字符串s的长度
dp = new Boolean[sLength + 1][pLength + 1]; // 保存中间计算结果的数组
return isMatch(s, p, 0, 0); // 分别从s和p的第0位开始匹配
}
public boolean isMatch(String s, String p, int sIndex, int pindex) {
// 如果匹配字符串p的当前位置已经超过最后一位(p已经消耗完)
if (pindex >= pLength) {
// 这时如果s还有剩余，那么一定无法完整匹配，返回false。反之则完全匹配
return sIndex >= sLength;
}
// 如果对应的sIndex和pindex的计算结果不为空，直接返回该结果。
if (dp[sIndex][pindex] != null) {
return dp[sIndex][pindex];
}
// 当前pindex对应的字符
char charP = p.charAt(pindex);
// 当前sIndex对应的字符，注意越界。如果越界，charS定义为'-'
char charS = (sIndex < sLength) ? s.charAt(sIndex) : '-';
// p当前位的下一个字符为星号的情况
if (pindex + 1 < pLength && p.charAt(pindex + 1) == '*') {
// 1. s当前字符等于p当前字符，或者p当前字符为'.'，递归比较pindex与sIndex + 1
// 2. 忽略掉p的当前字符以及之后的星号，递归比较pindex + 2与sIndex
// 上述两种情况一真则真
dp[sIndex][pindex] = sIndex < sLength && (charS == charP || charP == '.')
&& isMatch(s, p, sIndex + 1, pindex) || isMatch(s, p, sIndex, pindex + 2);
return dp[sIndex][pindex];
} else {
// p当前位的下一个字符不是星号的情况，
// 比较当前位是否相同，并递归看下一位是否相同
dp[sIndex][pindex] = sIndex < sLength && (charS == charP || charP == '.')
&& isMatch(s, p, sIndex + 1, pindex + 1);
return dp[sIndex][pindex];
}
}
其实LeetCode中还有一题与本题非常相似，同样可以利用此方法来思考，大家可以自己练习一下。题号 44. Wildcard Matching。同时这道题还有另外一种解法，有兴趣可以参考另外一篇文章：
leetcode 44. Wildcard Matching 解题思路分析
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-10-regular-expression-matching解题思路分析/