剑指offer系列之五十一：正则表达式匹配

本文主要是介绍剑指offer系列之五十一：正则表达式匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配

由于只涉及两种正则表达式的匹配，所以关键是需要分清除匹配的所有情况，对于模式串来讲，出现了’.’和’*’的时候需要单独考虑，因为两者的匹配情况是不一样的。先考虑模式串中有’*’的情况，因为’*’可以匹配0个或者多个，所以如果模式串的下一个字符是’*’的时候就有三种情况：1）匹配0个主串的字符，比如主串是abc，模式串是b*的时候，就是这种情况，那么下一步的匹配策略是主串保持不变，模式串跳到下两个字符重新比较；2）匹配1个字符，比如主串是abc，模式串是a*就是这种情况，因为只匹配到了a这一个字符。这种情况的下一步的比较策略应该是主串跳到下一个字符，模式串移动两个位置；3）匹配多个字符，比如主串是aac，模式串是a*cb就匹配到了aa这两个字符，那么这种情况下下一步的匹配策略应该是主串移动一个字符，模式串移动两个位置；如果当前的字符与主串的字符不能匹配，则主串保持不变，模式串移动两个位置。如果当前字符是’.’的话，直接逐个字符进行比较就行了。下面是这种思路的实现代码（已被牛客AC）：

package com.rhwayfun.offer;public class MatchRegString {public boolean match(char[] str, char[] pattern) {if (str == null || pattern == null)return false;return matchRegCore(str, 0, str.length, pattern, 0, pattern.length);}private boolean matchRegCore(char[] str, int i, int length1,char[] pattern, int j, int length2) {if (i == length1 && j == length2) {// 主串匹配到末尾，模式串要么也匹配到末尾要么当前位置的字符是*，否则返回falseif (j == length2 || pattern[j] == '*')return true;elsereturn false;}if (i != length1 && j == length2)return false;/** 一、如果模式串的下一个字符是*， 1.1 并且模式串的当前字符能与主串的字符进行匹配，则可能出现三种情况：* 1、模式串的当前字符匹配到0个字符，则主串不变，模式穿移动到两个字符* 2、模式穿的当前字符匹配到1个字符，则主串移动一个位置，模式串移动两个位置* 3、模式串的当前字符匹配到多个字符，则主串移动一个位置，模式串移动两个位置。 1.2 如果不能匹配的话: 主串不变，模式串移动两个位置；* 二、如果下一个字符不是*，则进行逐个字符进行匹配 三、如果模式串的下一个字符是.，则就进行一个字符的匹配*/if (j + 1 < length2 && pattern[j + 1] == '*') {if (i < length1 && (pattern[j] == str[i] || pattern[j] == '.')) {return matchRegCore(str, i + 1, length1, pattern, j, length2)|| matchRegCore(str, i + 1, length1, pattern, j + 2,length2)|| matchRegCore(str, i, length1, pattern, j + 2,length2);} else {return matchRegCore(str, i, length1, pattern, j + 2, length2);}}if (i < length1 && (str[i] == pattern[j] || pattern[j] == '.')) {return matchRegCore(str, i + 1, length1, pattern, j + 1, length2);}return false;}public static void main(String[] args) {char[] str = { 'a', 'a', 'a' };char[] pattern = { 'a', 'b', '*', 'a' };boolean b = new MatchRegString().match(str, pattern);System.out.println(b);}
}