时间：2020-07-01 题目： 请实现一个函数用来匹配包括’.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
思路：相当于实现new String(str).matches(new String(pattern)); 方法一：递归 ".*"能和任意长度的任意字符匹配，Java要随时检查是否越界 假设主串为s，长度为sn， 模式串为p，长度为pn，设置两个指针，sx和px，一开始sx=px，因为'*'前面的字符可以出现任意次，索引我们先按p[px+1]是否为'*'来分类 1. p[px+1]！=’*’：
如果p[px]为正常字符， 那么我们看是s[sx]是否等于p[px], 如果相等，说明当前位匹配成功,接下来sx+1，px+1，如果不相等直接返回false如果p[px] 为'.', 它能匹配任意字符，接下来sx+1，px+1 2. p[px+1]==’*’：有两种情况如果K在s中重复0次【就算当前p[px]==s[sx]或者p[px]=='.'也可以看成重复0次（eg:"aa","aa*a"）】，则pattern数组直接跳过两个,sx不变，px+2如果p[px]重复一次或者多次,也就是至少一次，那么条件是p[px]==s[sx]或者p[px]=='.'，然后一个一个去匹配，sx+1,px不变最后返回以上两种情况的“或” 递归终止条件：两方同时结束：返回true；pattern先到尾：返回falsestring先到尾：继续，因为pattern可能剩下一些x* 方法二：动态规划 boolean数组match[sx][px]表示长度为sx的s的子串和长度为px的p的子串是否成功匹配，对应当前s和p的元素为：s[sx-1]和p[px-1] 分情况讨论： 1. p[px-1]！=’*’：p[px-1]==s[sx-1]或者p[px-1]=='.'，说明当前位匹配成功,那么match[sx][px]=match[sx-1][px-1]，如果不相等直接match[sx][px]=false【boolean数组默认初始化为false】 2. p[px-1]==’*’：p[px-2]==s[sx-1]或者p[px-2]=='.'，那么s[sx-1]可能会重复0次【eg：“aa”,"aaa"直接把"x"砍掉，取决于match[sx][px- 2]】或者多次（>=1）【取决于match[sx-1][px]】，match[sx][px]=match[sx][px-2] || match[sx-1][px]否则，直接把"x*"砍掉：match[sx][px]=match[sx][px-2] 数组初始化：s的空字符串可以匹配p的空字符串：match[0][0]=true;s的空字符串还可以匹配"abc*…":所以应该把match[0][x](对应p[x-1])这样初始化： p[x-1]!="*"，match[0][x]=false【默认值】p[x-1]=="*"，match[0][x]=match[0][x-2]；Java代码
/** * @author LiMin * @Title: Match * @Description: 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 * 在本题中，匹配是指字符串的所有字符匹配整个模式。 * @date 2020/7/2 21:12 */ public class Match { public static void main(String[] args) { char[] string = " ".toCharArray(); char[] pat = " ".toCharArray(); Match m = new Match(); System.out.println(m.matchTwo("aa".toCharArray(), "aa*a*a".toCharArray())); } /** * 递归法 */ public boolean matchOne(char[] str, char[] pattern) { if (str == null || pattern == null) { return false; } int sx = 0; int px = 0; return matchhelper(str, sx, pattern, px); } public boolean matchhelper(char[] str, int sx, char[] pattern, int px) { //先列出递归终止条件 //同时结束 if (sx == str.length && px == pattern.length) { return true; } //pattern先结束 if (sx != str.length && px == pattern.length) { return false; } //现在只剩下px<pattern.length的情况 if (px + 1 < pattern.length && pattern[px + 1] == '*') {//pattern有下一个符号，且下一个符号为* if (sx != str.length && (str[sx] == pattern[px] || pattern[px] == '.')) { return matchhelper(str, sx, pattern, px + 2)//匹配0次,pattern直接跳过两个字符，即"x*" || matchhelper(str, sx + 1, pattern, px);//匹配1次或多次，一个一个往后匹配 } else { return matchhelper(str, sx, pattern, px + 2);//匹配0次,pattern直接跳过两个字符，即"x*" } } else {//pattern有下一个符号，且下一个符号不为*或者pattern没有下一个符号，即px==pattern.length-1 if (sx != str.length && (str[sx] == pattern[px] || pattern[px] == '.')) { return matchhelper(str, sx + 1, pattern, px + 1); } else { return false; } } } /** * 动态规划 */ public boolean matchTwo(char[] str, char[] pattern) { if (str == null || pattern == null) { return false; } boolean[][] match = new boolean[str.length + 1][pattern.length + 1];//boolean默认初始化为false match[0][0] = true;//空字符串和空字符串相匹配，还和"a*b*c*.."类型的相匹配 for (int i = 1; i <= pattern.length; i++) { if (pattern[i - 1] == '*') { match[0][i] = match[0][i - 2]; } } //match[sx][px]对应当前s和p的元素为：s[sx-1]和p[px-1] for (int sx = 1; sx <= str.length; sx++) { for (int px = 1; px <= pattern.length; px++) { if (pattern[px - 1] == '.' || str[sx - 1] == pattern[px - 1]) {//当前元素相匹配 match[sx][px] = match[sx - 1][px - 1]; }//str[sx-1]!=pattern[px-1]时默认match[sx][px]为false else if (pattern[px - 1] == '*') { if (pattern[px - 2] == '.' || str[sx - 1] == pattern[px - 2]) {//可能重复0次或者多次 match[sx][px] = match[sx][px - 2] || match[sx - 1][px]; } else { match[sx][px] = match[sx][px - 2]; } } } } return match[str.length][pattern.length]; } }