《剑指offer》—— 52. 正则表达式匹配（Java）
推荐
完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版
题目描述
请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。
public class Solution {
public boolean match(char[] str, char[] pattern)
{
}
}
思路：
模式中的 ‘ . ’ 可以任意一个字符，这个比较好处理，加一个 || 判断即可。
难处理的是模式中的 ‘*’ ，‘*’ 表示它前面的字符可以出现任意次（包含0次）。
我们根据有和没有 ‘*’ ，分成两大类情况来处理。
Ⅰ、 模式中的第二个字符是 “*” 时。
-
如果字符串中第一个字符与模式中第一个字符不匹配，字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 匹配 0 个字符，跳过模式中的这两个字符。
-
如果字符串中第一个字符与模式中第一个字符匹配，又可分为以下3种子情况来处理：
2.1 字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 还是匹配了 0 个字符；
2.2 字符串中的下标后移 1 位，模式中的下标后移 2 位，相当于 x* 匹配 1 个字符
2.3 字符串中的下标后移 1 位，模式中的下标不后移，相当于 x* 匹配了 1 个字符之后，还可能可以匹配串中的下一个字符
Ⅱ、模式中的第二个字符不是 “*” 时。
- 字符串中第 1 个和模式中第 1 个匹配，则字符串和模式中的下标都后移 1 位；
- 字符串中第 1 个和模式中第 1 个不匹配，直接返回 false。
实现：
public class Solution {
public boolean match(char[] str, char[] pattern)
{
if (str == null || pattern == null){
return false;
}
//字符串中的下标
int strIndex = 0;
//模式中的下标
int patternIndex = 0;
return checkMatch(str, strIndex, pattern, patternIndex);
}
public boolean checkMatch(char[] str, int strIndex, char[] pattern, int patternIndex) {
//如果字符串和模式长度都为0了，都到结尾了，则匹配成功，返回true
if(strIndex == str.length && patternIndex == pattern.length) {
return true;
}
//如果patter长度先为0，而字符串长度还没有为0，也就是模式先到结尾，而字符串还有没匹配的，说明匹配失败，返回false
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
//模式第2个是 * ，如果字符串中第 1 个和模式中第 1 个匹配，分 3 中匹配模式； 如果第 1 个不匹配，模式后移 2 位；
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
//字符串中第 1 个和模式中第 1 个匹配
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')) {
//3种匹配模式
return checkMatch(str, strIndex, pattern, patternIndex + 2) //字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 匹配 0 个字符
// 字符串中的下标后移 1 位，模式中的下标后移 2 位，相当于 x* 匹配 1 个字符
|| checkMatch(str, strIndex + 1, pattern, patternIndex + 2)
// 字符串中的下标后移 1 位，模式中的下标不后移，相当于 x* 匹配了 1 个字符之后，还可能可以匹配串中的下一个字符
|| checkMatch(str, strIndex + 1, pattern, patternIndex);
} else {
//字符串中第 1 个和模式中第 1 个不匹配，字符串中的下标不后移，模式中的下标后移 2 位，相当于 x* 匹配 0 个字符，跳过模式中的这两个字符。
return checkMatch(str, strIndex, pattern, patternIndex + 2);
}
}
//模式第2个不是 * ，且字符串中第 1 个和模式中第 1 个匹配，则都后移 1 位；
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (strIndex != str.length && pattern[patternIndex] == '.')) {
return checkMatch(str, strIndex + 1, pattern, patternIndex + 1);
}
//模式第2个不是 * ，且字符串中第 1 个和模式中第 1 个不匹配，直接返回 false。
return false;
}
}
看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。
这里是猿兄，为你分享程序员的世界。
非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！
注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！
