【困难】字符串匹配问题－Java：递归解法

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.String; /** * 字符串匹配问题 * * 【题目】 * 给定字符串str其中绝对不含有字符.和*。再给定字符串exp其中可以含有.或**字符不能是exp的首字符并且 * 任意两个*字符不相邻。exp中的.代表任何一个字符exp中的*表示*的前一个字符可以有0个或者多个。请写一个函数 * 判断str是否能被exp匹配。 * * 【难度】 * 困难 * * 【解答】 * 首先解决str和exp有效性的问题。根据描述str中不能含有.和*exp中*字符不能是首字符并且任意两个*字符不相 * 邻。具体请参看如下代码中的isValid方法。 * * 接下来看如何用递归方法来解这道题如下代码中的isMatch方法是递归解法的主函数process方法是递归的主要过程先列出代 * 码然后详细解释过程。 * * 下面解释一下递归过程process函数的意义是从str的si位置开始一直到str结束位置的子串即str[si..slen]是否能被 * 从exp的ei位置开始一直到exp结束位置的子串(即exp[ei..elen])匹配所以process(s,e,0,0)就是最终返回的结果。 * 那么在递归过程中如何判断str[si..slen]是否能被exp[ei..elen]匹配呢 * 假设当前判断到str的si位置和exp的ei位置即process(s,e,si,ei)。 * * 1.如果ei为exp的结束位置(eielen)si也是str的结束位置返回true因为可以匹配。如果si不是str的结束位置返 * 回false这是显而易见的。 * * 2.如果ei位置的下一个字符(e[ei1)不为*。那么就必须关注str[si]字符能否和exp[ei]字符匹配。如果str[si]与exp[ei] * 能匹配(e[ei]s[si]||e[ei].)还要关注str后续的部分能否被exp后续的部分匹配即process(s,e,si1,ei1)的 * 返回值。如果str[si]与exp[ei]不能匹配当前字符都匹配当然不用计算后续的直接返回false。 * * 3.如果当前ei位置的下一个字符(e[ei1])为*字符。 * 1)如果str[si]与exp[ei]不能匹配那么只能让exp[ei..ei1]这个部分为也就是exp[ei1]*字符的前一个字符 * exp[ei]的数量为0才行然后考查process(s,e,si,ei2)的返回值。 * 2)如果str[si]与exp[ei]能匹配exp[ei..ei1]的部分如果能匹配str后续很多位置的时候只要有一个返回true就可以直 * 接返回true。 * * 整体递归过程结束。 * * 在分析完如上递归过程之后来看递归函数的结构。我们很容易发现递归两数process(s,e,si,ei)在每次调用的时候有两个参数 * 是始终不变的(s和e)所以代表process函数状态的就是si和ei值的组合。所以如果把递归函数p在所有不同参数(si和ei)的情 * 况下的所有返回值看作一个范围这个范围就是一个(slen1)*(elen1)的二维数组并且p(si,ei)在整个递归过程中依赖的总 * 是p(sil,ei1)或者p(sik(k0),ei2)假设二维数组dp[i][j]代表p(i,j)的返回值dp[i][j]就只是依赖 * dp[i1][j1]或者dp[ik(k0)][j2]的值。进一步可以看出想要求dp[i][j]的值只需要(i,j)位置右下方的某些值。所 * 以只要从二维数组的右下角开始从右到左、再从下到上地计算出二维数组dp中每个位置的值就可以dp[0][0]就是最终的结果。 * p(i,j)的递归过程如何dp[i,j]的值就怎样去计算。这种方法实际上就是动态规划的方法省去了递归过程中很多重复计算的过程。 * * 先从右到左计算dp[slen][...]也就是二维数组dp中的最后一行dp[slen][elen]值的含义是str已经结束剩下的宇符串为 * exp也已经结束剩下的字符串为所以此时exp可以匹配strdp[slen][elen]true。对于dp[slen][0..elen-1]的 * 部分dp[slen][i]的含义是str已经结束剩下的字符串为exp却没有结束剩下的字符串为exp[i..elen-1]什么情况下 * exp[i..elen-1]可以匹配只能是不停地重复出现X*知这种方式。也就是说在从右向左计算dp[slen][0..elen-1]的过 * 程中看exp是不是从右往左重复出现X*如果是重复出现那么如果exp[i]Xexp[i1]*令dp[slen][i]true * 如果exp[i]*exp[i1]X令dp[slen][i]false。如果不是重复出现最后一行后面的部分(即dp[slen][0..i]) * 全都是false。这样就搞定了dp[][]最后一行的值。 * * 再看看dp[][]除右下角的值之外最后一列其他位置的值即dp[0..slen-1][elen]。这表示如果exp已经结束而str还没结 * 束显然exp为匹配不了任何非空字符串所以dp[0..slen-1][elen]都为false。 * * 接着看dp[][]倒数第二列的值即dp[0..slen-1][elen-1]。这表示如果exp还剩一个字符即(exp[elen-1])而str还剩1个 * 字符或多个字符。很明显str还剩多个字符的情况下exp匹配不了。str还剩1个字符的情況下(即str[slen-1])如果和 * exp[elen-1]相等则可以匹配或者exp[elen-1].的情况下可以匹配。 * * 因为dp[i][j]只依赖dp[i1][j1]或者dp[ik][j2](k0)的值所以在单独计算完最后一行、最后一列与倒数第二列之后 * 剩下的位置在从右到左、再从下到上计算dp值的时候所有依赖的值都被计算出来直接拿过来用即可。如果str的长度为Nexp的 * 长度为M因为有枚举的过程所以时间复杂度为O(N^2×M)额外空间复杂度为O(NXM)。 * * 具体请参看如下代码中的isMatchDP方法。 * * author Created by LiveEveryDay */ public class StringMatchProblem1 { public static boolean isValid(char[] s, char[] e) { for (int i 0; i s.length; i) { if (s[i] * || s[i] .) { return false; } } for (int i 0; i e.length; i) { if (e[i] * (i 0 || e[i - 1] *)) { return false; } } return true; } public static boolean isMatch(String str, String exp) { if (str null || exp null) { return false; } char[] s str.toCharArray(); char[] e exp.toCharArray(); return isValid(s, e) ? process(s, e, 0, 0) : false; } public static boolean process(char[] s, char[] e, int si, int ei) { if (ei e.length) { return si s.length; } if (ei 1 e.length || e[ei 1] ! *) { return si ! s.length (e[ei] s[si] || e[ei] .) process(s, e, si 1, ei 1); } while (si ! s.length (e[ei] s[si] || e[ei] .)) { if (process(s, e, si, ei 2)) { return true; } si; } return process(s, e, si, ei 2); } public static void main(String[] args) { String str cdCCDDEE; String exp c.C*D*E*; System.out.printf(Does it match? %b, isMatch(str, exp)); } } // ------ Output ------ /* Does it match? true */