思路及解答递归

如果pattern ⻓度为0且str ⻓度为0 ,说明刚刚好匹配完返回turestr ⻓度不为0 说明没有匹配完返回false如果pattern 的⻓度⼤于0如果pattern 的⻓度⼤于1 且第2 个字符是* 说明前⾯的字符可以匹配0 1 或者多次分为两种情况讨论⼀种是直接把* 和* 前⾯的字符去掉相当于匹配了0 个然后接着⽐较另外⼀种是如果str 的⻓度⼤于0 并且第⼀个字符匹配那就把str 的第⼀个字符去掉两者接着匹配。否则说明第⼆个字符不是 * 那么就直接⽐较第⼀个字符是不是匹配同时将后⾯的字符进⾏匹配。注意上⾯说的第⼀个字符是不是匹配除了两个字符相等的情况其实还有模式串的字符为 . 的情况。javapublic class Solution { public boolean isMatch(String s, String p) { // 模式串为空时文本串也必须为空才匹配 if (p.isEmpty()) return s.isEmpty(); // 检查首字符匹配文本串非空且字符相等或模式为. boolean firstMatch !s.isEmpty() (s.charAt(0) p.charAt(0) || p.charAt(0) .); // 处理*通配符确保模式长度≥2且第二个字符是* if (p.length() 2 p.charAt(1) *) { // 两种情况1) *匹配0个前驱字符 2) 匹配1个及以上前驱字符 return isMatch(s, p.substring(2)) || (firstMatch isMatch(s.substring(1), p)); } else { // 无*情况首字符匹配且剩余部分也匹配 return firstMatch isMatch(s.substring(1), p.substring(1)); } } }时间复杂度最坏O((mn)2^(mn))空间复杂度O(m²n²)递归栈记忆化搜索递归缓存在递归基础上添加缓存避免重复计算。使用二维数组存储s[i:]和p[j:]的匹配结果避免重复递归javapublic class Solution { private Boolean[][] memo; // 缓存数组null未计算true/false已计算 public boolean isMatch(String s, String p) { memo new Boolean[s.length() 1][p.length() 1]; return dfs(0, 0, s, p); } private boolean dfs(int i, int j, String s, String p) { // 检查缓存是否存在当前子问题的解 if (memo[i][j] ! null) return memo[i][j]; boolean result; // 模式串耗尽时文本串也必须耗尽 if (j p.length()) { result (i s.length()); } else { // 计算当前首字符匹配状态 boolean firstMatch (i s.length()) (s.charAt(i) p.charAt(j) || p.charAt(j) .); // 处理*通配符 if (j 1 p.length() p.charAt(j 1) *) { result dfs(i, j 2, s, p) || // 匹配0次 (firstMatch dfs(i 1, j, s, p)); // 匹配1次 } else { result firstMatch dfs(i 1, j 1, s, p); } } memo[i][j] result; // 存储结果到缓存 return result; } }时间复杂度O(m×n)空间复杂度O(m×n)动态规划推荐动态规划⾸先定义状态⽤⼀个⼆维数组套路dp[i][j]⽤来表示str 的前i 个字符和pattern 的前j 个字符是否匹配。初始化简单状态dp[0][0] true,表示两个空的字符串是匹配的。dp 数组的⾸列除了dp[0][0] 为true其他的都是false 。因为pattern 为空但是s 不为空的时候肯定不匹配。dp 的⾸⾏也就是str 为空的时候如果pattern 的偶数位都是“*”,那么就可以匹配因为可以选择匹配0 次。初始化前⾯之后后⾯的从索引1 开始匹配pattern 的第j 个字符为“ * ”(即是pattern[j-1]*)如果dp[i][j-2]true那么dp[i][j]true(相当于str的前i和pattern的前j-2个字符匹配此时的* 前⾯的那个字符出现了0 次)。如果dp[i-1][j]true且str[i-1]pattern[j-2]则dp[i][j] true。如果str 的前i - 1 个字符和pattern 的前j 个字符匹配并且str 的第i 个字符和pattern 的第j - 1 个字符相等,相当于‘ * ’前⾯的字符出现了1 次如果dp[i-1][j]true且pattern[j-2].的时候则dp[i][j]true。(表示str 的前i-1 个和patten 的前j 个匹配并且pattern 的第j-1 个是‘ . ’第j 个是‘ * ’,那么说明可以匹配任何字符任何次数⾃然str 可以多匹配⼀个字符。)pattern 的第j 个字符不为“ * ”(即是pattern[j-1]*)如果dp[i - 1][j - 1]true and str[i - 1] pattern[j - 1]时则dp[i][j]true。也就是前⾯匹配接下来的字符⼀样匹配如果dp[i - 1][j - 1]true且pattern[i-1].那么dp[i][j]true。(其实也是. 可以匹配任何字符)处理完数组之后最后返回dp[n-1][m-1]也就是str 的前n 个和pattern 的前m 个字符是否匹配。javapublic boolean match(String str, String pattern) { if (pattern.length() 0) { return str.length() 0; } int n str.length() 1; int m pattern.length() 1; boolean[][] dp new boolean[n][m]; dp[0][0] true; for (int j 2; j m; j j 2) { if (dp[0][j - 2] pattern.charAt(j - 1) *) { dp[0][j] true; } } for (int i 1; i n; i) { for (int j 1; j m; j) { if (pattern.charAt(j - 1) *) { dp[i][j] dp[i][j - 2] || dp[i - 1][j] (str.charAt(i - 1) pattern.charAt(j - 2) || pattern.charAt(j - 2) .); } else { dp[i][j] dp[i - 1][j - 1] (str.charAt(i - 1) pattern.charAt(j - 1) || pattern.charAt(j - 1) .); } } } return dp[n - 1][m - 1]; }时间复杂度 O(mn) 其中 m , n 分别为 str 和 pattern 的⻓度状态转移需遍历整个 dp 矩阵。空间复杂度 O(mn) 状态矩阵 dp 使⽤ O(mn) 的额外空间。状态机优化空间优化DP状态机优化滚动数组降低空间复杂度只保留当前行和上一行的状态空间优化到O(n)javapublic class Solution { public boolean isMatch(String s, String p) { int m s.length(), n p.length(); boolean[] dp new boolean[n 1]; boolean[] prev new boolean[n 1]; // 初始化第一行空文本串情况 dp[0] true; for (int j 2; j n; j) { if (p.charAt(j - 1) *) { dp[j] dp[j - 2]; } } for (int i 1; i m; i) { // 保存上一行状态 boolean[] temp prev; prev dp; dp temp; // 初始化当前行首列 dp[0] false; for (int j 1; j n; j) { char sc s.charAt(i - 1); char pc p.charAt(j - 1); if (pc *) { char prevChar p.charAt(j - 2); boolean matchZero dp[j - 2]; boolean matchMulti (prevChar sc || prevChar .) prev[j]; dp[j] matchZero || matchMulti; } else { dp[j] (pc . || pc sc) prev[j - 1]; } } } return dp[n];