本文共 1320 字，大约阅读时间需要 4 分钟。

leetcode 0010

说明

只是为了记录一下，不求多快，也不深究。

会简要描述思路，代码中不写注释。

如碰到不会做的用了别人代码会在博客中标出。

题目描述

结果

参考

参考了B站up主Dubliner的讲解，下面是那个视频的链接：

思路

一碰到难度是困难的就不会做了。

用动态规划

dp[ i ][ j ]代表了s的前i个字符和p的前j个字符是否匹配，算上0的话，显然dp的大小是(s.length()+1)*(p.length()+1)。

dp[0][0]两个字符都是空，匹配，设为true。当s不为空，p为空时，显然是false。

当s为空，p不为空时，因*有将字符串变空的能力，若遇到*时，dp[0][j] = dp[0][j-2]，p的首字符不为*,因此不用担心越界。

初始化完成，下面说明状态转移的办法：

• 如果si和pj相等或者pj等于‘.’的话，就看i和j之前的字符串是否匹配。

• 如果不相等的话

  • 有一种情况是pj是*,在这种情况下

    • 若si和pj-1不相等，因*可抹去一个字符，故就看i和j-2之前字符串是否匹配；
    • 若si和pi-1相等，那*的作用既可能是增加，也可能是抹去，比如“aa”和“a*”就是要增加，而“a”和“aa*”就是要抹去，此时dp[i ][j ] = dp[i-1][j] || dp[i][j-2]。

  • 最后一种情况就是pj也是字母，但不和si相等，直接false，不可能匹配的。

代码

class Solution {       public boolean isMatch(String s, String p) {   		boolean[][] dp = new boolean[s.length()+1][p.length()+1];		dp[0][0] = true;		for(int i=1;i<=p.length();i++) {   			if(p.charAt(i-1)=='*') {   				dp[0][i] = dp[0][i-2];			}		}		for(int i=1;i<=s.length();++i) {   			for(int j=1;j<=p.length();++j) {   				if(s.charAt(i-1) == p.charAt(j-1)||p.charAt(j-1) == '.') {   					dp[i][j] = dp[i-1][j-1];				}else if(p.charAt(j-1) == '*') {   					if(s.charAt(i-1) == p.charAt(j-2)||p.charAt(j-2) == '.') {   						dp[i][j] = dp[i-1][j] || dp[i][j-2];					}else {   						dp[i][j] = dp[i][j-2];					}				}else {   					dp[i][j] = false;				}			}		}        return dp[s.length()][p.length()];    }}