1.本题知识点 字符串、递归 2. 题目描述 请实现一个函数用来匹配包括 . 和 * 的正则表达式。模式中的字符 . 表示任意一个字符，而 * 表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。 3. 思路 这题对编程来说没多大难度，难点是理解题目和考虑全面，总体感觉有点绕。 首先要明白，字符串和模式串是每个字符依次比较的。而且要弄懂 . 和 * 的意思。 一、当模式串中的第二个字符不是“*”时(这种情况其实就是将字符依次比较就行了)： 1、当前字符不相同： 直接返回false。 2、当前字符相同： 即不管是模式串和字符串相等，还是模式串为 . 时，都可以继续递归进入下一轮的匹配。 二、而当模式串中的第二个字符是“*”时： 1、当前字符不相同，跳过模式的当前字符和*，继续下一轮匹配。（这是*匹配0次的情况）如图，最终匹配成功：
2、当前字符相同, 又有两种情况： ① 模式后移2字符，相当于x*被忽略（这是*匹配0次的情况）。如图，最终匹配成功：
② 模式串不变，字符串后移1位（这是*匹配多次的情况）。如图，最终匹配成功：
Java版本： package com.algorithm.str;/** * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 * 在本题中，匹配是指字符串的所有字符匹配整个模式，则返回true。 * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配 * * @author wxq * */public class MatchPattern {public static void main(String[] args) {String str = "abbbaa";String pattern = "ab*baa";System.out.println(match(str.toCharArray(), pattern.toCharArray()));}/** * 匹配 * @param str * @param pattern * @return */static boolean match(char[] str, char[] pattern) {if (str == null || pattern == null) {return false;}int strIndex = 0;int patternIndex = 0;return matchCore(str, strIndex, pattern, patternIndex);}/** * 可将数组索引看作指针 * @param str * @param strIndex * @param pattern * @param patternIndex * @return */static boolean matchCore(char[] str, int strIndex, char[] pattern,int patternIndex) {// str到尾，pattern到尾，匹配成功if (strIndex == str.length && patternIndex == pattern.length) {return true;}// str没到尾，pattern先到尾，匹配失败if (strIndex != str.length && patternIndex == pattern.length) {return false;}// 模式串第2个字符是*if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {//递归条件：当前字符相同，或者模式串当前字符为 . if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])|| (strIndex != str.length && pattern[patternIndex] == '.' )) {return matchCore(str, strIndex, pattern, patternIndex + 2) // 模式串pattern后移2，str指针不变，即x*匹配了0个字符|| matchCore(str, strIndex + 1, pattern, patternIndex);// 模式串pattern指针不变 ,str后移1位}//如果当前字符不相同,则跳过当前模式串的字符和* ，继续下一轮的匹配else{return matchCore(str, strIndex, pattern, patternIndex + 2);}}//模式串第2个字符不是 * ，这种情况其实就依次比较字符即可if (strIndex != str.length) {//字符串和模式串当前字符相同，或者模式串当前字符为 . 时，同时后移1位，继续下一轮的匹配if(pattern[patternIndex] == str[strIndex] || pattern[patternIndex] == '.'){return matchCore(str, strIndex + 1, pattern, patternIndex + 1);}}return false;}}