经典动态规划：正则表达式 :: labuladong的算法小抄 #1026
Replies: 20 comments 9 replies
-
|
补充一下dp写法 def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
if p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 2]
if s[i - 1] == p[j - 2] or p[j - 2] == '.':
dp[i][j] |= dp[i - 1][j]
return dp[m][n] |
Beta Was this translation helpful? Give feedback.
-
|
dp也可以表达 S[i...] 和 P[j...] 是否匹配。 bool dp(string &s, int i, string &p, int j, int memo[20][30]){
// match
if(i == s.length() && j == p.length()){
return true;
}
// any side has char left will be considered mismatch
if(i > s.length() || j > p.length()){
return false;
}
if (memo[i][j] != -1){
return memo[i][j];
}
bool isStar = j < p.length() && p[j+1] == '*';
if (!isStar){
if(p[j] == '.' || p[j] == s[i]){
memo[i][j] = dp(s, i+1, p, j+1, memo);
}else {
memo[i][j] = false;
}
return memo[i][j];
}
// the next char in P is *
bool isMatch = false;
if (p[j] == '.' || p[j] == s[i]){
// one or multiple match
isMatch = dp(s, i+1, p, j+2, memo) || dp(s, i+1, p, j, memo);
}
//1. zero match
memo[i][j] = dp(s, i, p, j+2, memo) || isMatch;
return memo[i][j];
} |
Beta Was this translation helpful? Give feedback.
-
|
这个会有测试用例过不了吧？ |
Beta Was this translation helpful? Give feedback.
-
|
我用c++写的，用int类型的-1初始化的memo，最后过了，从逻辑上讲，我觉得并不需要额外的判断当aa...a*的这种情况，以上结束条件可以完美覆盖 |
Beta Was this translation helpful? Give feedback.
-
|
jave 代码 class Solution {
boolean[][] memo;
public boolean isMatch(String s, String p) {
int m = s.length(),n=p.length();
memo = new boolean[m][n];
for(int i=0;i<m;i++){
Arrays.fill(memo[i],false);
}
return dp(s,0,p,0);
}
boolean dp(String s, int i, String p, int j){
int m = s.length(),n=p.length();
//base case
if(j == n){
return i == m;
}
if(i == m){
if((n-j)%2 == 1){
return false;
}
for(;j+1<n;j+=2){
if(p.charAt(j+1) != '*'){
return false;
}
}
return true;
}
if(memo[i][j]!= false){
return memo[i][j];
}
boolean res = false;
if(s.charAt(i) == p.charAt(j)||p.charAt(j)=='.'){
if(j+1<n && p.charAt(j+1)=='*'){
res = dp(s,i,p,j+2) || dp(s,i+1,p,j);
}else{
res = dp(s,i+1,p,j+1);
}
}else{
if(j+1<n && p.charAt(j+1)=='*'){
res = dp(s,i,p,j+2);
}else{
res = false;
}
}
memo[i][j] = res;
return res;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
打卡打卡。这个清楚！ |
Beta Was this translation helpful? Give feedback.
-
|
迭代+空间压缩 public class Solution {
public bool IsMatch(string s, string p) {
bool before, tmp;
bool[] dp = new bool[p.Length + 1];
dp[0] = true;
for (int j = 1; j <= p.Length; j++) {
if (p[j - 1] == '*') dp[j] = dp[j - 2];
}
before = dp[0];
dp[0] = false;
for (int i = 0; i < s.Length; i++) {
for (int j = 1; j <= p.Length; j++) {
tmp = dp[j];
if (s[i] == p[j - 1] || p[j - 1] == '.') {
dp[j] = before;
}
else if (p[j - 1] == '*') {
if (s[i] == p[j - 2] || p[j - 2] == '.') {
dp[j] |= dp[j - 2];
}
else dp[j] = dp[j - 2];
}
else dp[j] = false;
before = tmp;
}
before = dp[0];
}
return dp[p.Length];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
Java DP写法 class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
int m = s.length(), n = p.length();
//dp[i][j] 表示 s[i] 是否与 p[j] 匹配
boolean[][] dp = new boolean[m + 1][n + 1];
//base case
dp[0][0] = true;
//s[0] == null 所以 p[j] == * 将 *号前面的字符删除 ， 则可以匹配 * 可以表示 将前面的一个字符删除
//所以 dp[0][j] 依赖于 dp[0][j-2]
for(int j = 2; j<=n;j +=2){
if(p.charAt(j-1)=='*'){
dp[0][j] = dp[0][j-2];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if(s.charAt(i-1) == p.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else if(p.charAt(j-1)=='.'){
dp[i][j] = dp[i-1][j-1]; // p 的 . 与 s[i] 互相抵消 当前位置的dp 依赖之前结果
}else if(p.charAt(j-1) == '*'){
dp[i][j] = dp[i][j-2];
if(p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.'){
dp[i][j] = dp[i-1][j]||dp[i][j]; //p不动， s[i] 依赖 s[i-1]
}
}
}
}
return dp[m][n];
}
}
|
Beta Was this translation helpful? Give feedback.
-
|
Go DP func isMatch(s string, p string) bool {
sl := len(s)
pl := len(p)
dp := make([][]bool, sl+1)
for i := range dp {
dp[i] = make([]bool, pl+1)
}
dp[0][0] = true
for i := 1; i <= sl; i++ {
for j := 1; j <= pl; j++ {
// current chars are matching
if s[i-1] == p[j-1] || p[j-1] == '.' {
// if previous 0 ~ s[i-2] and 0 ~ p[i-2] are matching
// current 0 ~ s[i-2] and 0 ~ p[i-2] are matching
if dp[i-1][j-1] {
dp[i][j] = true
} else {
// if previous 0 ~ s[i-2] and 0 ~ p[i-2] are not matching
// if prev char is availale, and the prev is "*"
// like b*b*a and a,
// b*b* and "" could match by using * to remove "b"
// j >= 3 to make sure we could remove at least on pattern of b*
if j-3 >= 0 && p[j-2] == '*' {
m := j - 2
// skip all patterns like b*
for m >= 0 && p[m] == '*' {
m -= 2
}
if dp[i-1][m+1] {
dp[i][j] = true
}
}
}
}
// current chars are not matching
if s[i-1] != p[j-1] {
if p[j-1] == '*' {
// current * could remove previous char
// matching when remove curr and prev char in p
// look if s0~s[i-1] matches p0~p[j-3]
if dp[i][j-2] {
dp[i][j] = true
}
// matching when don't use both s[i-1] and p[j-1]
// s0 ~ s[i-2] matches p0 ~ pi-2
// s[i-1] == p[j-2] or p[j-2] == "."
// p[j-1] is a duplicate of p[j-2] or "."
if dp[i-1][j-1] && (s[i-1] == p[j-2] || p[j-2] == '.') {
dp[i][j] = true
}
// matching when don't use p[j-1]
// s0 ~ s[i-1] matches p0 ~ p[j-2]
// if s[i-1] == p[j-2], or p[j-2] is "."
// p[j-1] is a duplicate of p[j-2] or "."
if dp[i][j-1] && (s[i-1] == p[j-2] || p[j-2] == '.') {
dp[i][j] = true
}
// matching when don't use s[i-1]
// s0 ~ s[i-2] matches p0 ~ p[j-1]
// if s[i-1] == s[i-2], or p[j-2] is "."
// p[j-1] is two or more duplicate of p[j-2] or "."
if dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.') {
dp[i][j] = true
}
}
}
}
}
return dp[sl][pl]
} |
Beta Was this translation helpful? Give feedback.
-
|
楼上java代码感觉还能优化，因为boolean只有TF两种状态，但是如果判断过是false，还是会走一遍判断，所以用int数组引入-1,0,1三种状态分别代表未判断，已判断为F，已判断为T更好点 class Solution {
int[][] memo;
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dp(s, 0, p, 0);
}
boolean dp(String s, int i, String p, int j) {
int m = s.length(), n = p.length();
//pattern to the last while input no => false;
if (j == n) {
return i == m;
}
if (i == m) {
if ((n - j) % 2 == 1)
return false;
for (; j + 1 < n; j += 2) {
if (p.charAt(j + 1) != '*') {
return false;
}
}
return true;
}
if (memo[i][j] != -1)
return memo[i][j] == 1 ? true : false;
boolean res = false;
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
//* can replace more than 1 or 0;
if (j < n - 1 && p.charAt(j + 1) == '*') {
res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j);
} else {
// normal situation
res = dp(s, i + 1, p, j + 1);
}
} else {
if (j < n - 1 && p.charAt(j + 1) == '*') {
res = dp(s, i, p, j + 2);
} else {
res = false;
}
}
memo[i][j] = res == true ? 1 : 0;
return res;
}
} |
Beta Was this translation helpful? Give feedback.
-
go写法，抄了楼上大佬的。。。记忆化递归 func isMatch(s string, p string) bool {
memo := [][]int{}
for i := 0; i < len(s); i++ {
row := []int{}
for j := 0; j < len(p); j++ {
row = append(row, -888)
}
memo = append(memo, row)
}
if dp(s, p, 0, 0, memo) == 1 {
return true
} else {
return false
}
}
func dp(s string, p string, idx1, idx2 int, memo [][]int) int {
if idx1 == len(s) && idx2 == len(p) {
return 1
}
if idx1 == len(s) && idx2 < len(p) {
/*
todo 看看查多少
看看不是间隔一个字符都是*
*/
if (len(p) - idx2)%2 ==1 {
return 0
}
for i := idx2; i < len(p); i+=2 {
if p[i+1] != '*'{
return 0
}
}
return 1
}
if idx1 < len(s) && idx2 == len(p) {
return 0
}
if memo[idx1][idx2] != -888 {
return memo[idx1][idx2]
}
memo[idx1][idx2] = 0
if s[idx1] == p[idx2] || p[idx2] == '.' {
if idx2+1 < len(p) && p[idx2+1] == '*' {
//匹配0次
if dp(s, p, idx1, idx2+2, memo) == 1 ||
//匹配多次
dp(s, p, idx1+1, idx2, memo) == 1 {
memo[idx1][idx2] = 1
} else {
memo[idx1][idx2] = 0
}
} else {
memo[idx1][idx2] = dp(s, p, idx1+1, idx2+1, memo)
}
} else {
if idx2+1 < len(p) && p[idx2+1] == '*' {
//此时只能尝试匹配0次
memo[idx1][idx2] = dp(s, p, idx1, idx2+2, memo)
} else {
memo[idx1][idx2] = 0
}
}
return memo[idx1][idx2]
} |
Beta Was this translation helpful? Give feedback.
-
|
东哥，思路分析底下1.2 或许有个typo么？p[i] -> p[j] |
Beta Was this translation helpful? Give feedback.
-
|
感谢反馈~ |
Beta Was this translation helpful? Give feedback.
-
|
照着作者的递归 memo 写的自底向上 dp ： class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
// dp[i][j] 表示 s[i..] 是否匹配 p[j..]
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
// base case:
// 空串匹配空串
dp[m][n] = true;
// s[i..] 匹配空串为 false
for(int i = 0; i < m; i++) {
dp[i][n] = false;
}
// 空串匹配 p[j..]，主要看 p[j..] 是否是 x*z*y*.. 形式
for(int j = 0; j < n; j++) {
if((n-j) % 2 == 1)
dp[m][j] = false;
else {
bool res = true;
for(int jj = j; jj < n-1; jj += 2)
if(p[jj+1] != '*')
res = false;
dp[m][j] = res;
}
}
// 从后往前，dp[i][j] 需要的是其后面的元素
for(int i = m-1; i >= 0; i--) {
for(int j = n-1; j >= 0; j--) {
if(s[i] == p[j] || p[j] == '.') {
// “j+1 < n“ ，因为 n 此时有效，表示末尾的空串，需要考虑。
if(j+1 < n && p[j+1] == '*') {
dp[i][j] = dp[i][j+2] || dp[i+1][j];
}else {
dp[i][j] = dp[i+1][j+1];
}
}else {
// 同上
if(j+1 < n && p[j+1] == '*') {
dp[i][j] = dp[i][j+2];
}else {
dp[i][j] = false;
}
}
}
}
return dp[0][0];
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
比较简短的python版本 class Solution:
def matches(self,s,i: int,p, j: int) -> bool:
if p[j - 1] == '.':
return True
return s[i - 1] == p[j - 1]
def isMatch(self, s: str, p: str) -> bool:
# dp[i][j] = dp[i-1][j-1] ,s[i] == p[j] or p[j] == .
# dp[i][j] = dp[i-1][j] # match 1+ time if s[i] = p[j-1]/'.'
# dp[i][j] = dp[i][j-2] # match 0 time
dp = [[False for j in range(len(p)+1)] for i in range(len(s)+1)]
dp[0][0] = True
for i in range(0,len(dp)):
for j in range(1,len(dp[0])):
if p[j-1] == '*':
dp[i][j] = dp[i][j-2]
if self.matches(s,i,p,j-1):
dp[i][j] |= dp[i-1][j]
elif self.matches(s,i,p,j):
dp[i][j] = dp[i-1][j-1]
return dp[-1][-1] |
Beta Was this translation helpful? Give feedback.
-
|
基本按东哥思路来的 class Solution {
private int m, n;
private Boolean[][] memo;
public boolean isMatch(String s, String p) {
m = s.length();
n = p.length();
memo = new Boolean[m + 1][n + 1];
return isMatch(s, 0, p, 0);
}
/**
* 使用p[j:]模式能否匹配 s[i:]
*/
private boolean isMatch(String s, int i, String p, int j) {
if (memo[i][j] != null) {
return memo[i][j];
}
// base case
if (j == n) {
return i == m;
}
if (i == m) {
// s已匹配完，p[j:]必须能匹配空串，即匹配形如 a*b*
if ((n - j) % 2 == 1) {
return false;
}
for (; j + 1 < n; j += 2) {
if (p.charAt(j + 1) != '*') {
return false;
}
}
return true;
}
boolean res;
// 下个元素是否为*
boolean nextIsStar = j < n - 1 && p.charAt(j + 1) == '*';
// i为 s的下标，j为p的下标
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
// 仅适用.和精确匹配能匹配上
if (nextIsStar) {
// 下一个字符是*，匹配多个字符或0个字符
res = isMatch(s, i, p, j + 2) || isMatch(s, i + 1, p, j);
} else {
res = isMatch(s, i + 1, p, j + 1);
}
} else {
// 仅适用.和精确匹配无法匹配上
if (nextIsStar) {
// j+2 跳过*匹配
res = isMatch(s, i, p, j + 2);
} else {
res = false;
}
}
return memo[i][j] = res;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
c++空间压缩版本，dp[i]表示[i...]到末尾是否可以匹配 class Solution {
public:
bool isMatch(string s, string p) {
int m=s.size(), n=p.size();
if(m==0 && n==0) return true; //排除双空，因为下面要将dp[n]初始化为false，双空的时候因为不会进循环，会输出初始值，因此先排除；
vector<bool> dp(n+1, false); //注意 dp[n] = false, 二维数组的时候只有dp[m][n]=true 其他dp[i][n]=false;
//初始化
for(int i=n-1; i>=0; i-=2){
if( p[i] != '*') break;
else{
dp[i] = true;
if(i-1>=0) dp[i-1] = true;
}
}
bool tmp=true, dp_i1j1=true; // dp_i1j1存储二维空间中的dp[i+1][j+1]，tmp是临时变量
for(int i=m-1; i>=0; --i){
for(int j=n-1; j>=0; --j){
tmp = dp[j];
if(s[i] == p[j] || p[j] == '.'){
if(j+1<n && p[j+1] == '*'){
dp[j] = dp[j+2] || dp[j];
}else{
dp[j] = dp_i1j1;
}
}else{
if(j+1<n && p[j+1] == '*'){
dp[j] = dp[j+2];
}else{
dp[j] = false;
}
}
dp_i1j1 = tmp; //保存dp[i+1][j+1]的值供下次外层循环的时候使用
}
dp_i1j1 = false; //由于i的逆向遍历，因此下次dp_i1j1表示dp[i+1][n],应为false;
}
return dp[0];
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
C++版本, 自底向上,带空间压缩 |
Beta Was this translation helpful? Give feedback.
-
|
####看完东哥的题解，我有两个疑问####
#以上 |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
|
谢谢东哥 豁然开朗～ |
Beta Was this translation helpful? Give feedback.
-
|
java版dp |
Beta Was this translation helpful? Give feedback.
-
|
补充了一个完整的java实现 public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
// "" 空字符串 匹配上表达式 * 也要返回 true， 所以字符串s从0开始
for(int i = 0; i<= m; i++){
for(int j = 1; j <= n; j++){
char c = p.charAt(j-1);
if(c == '*'){
dp[i][j] = dp[i][j-2];
if(match(s, i, p, j-1)){
dp[i][j] = dp[i][j] | dp[i-1][j];
}
}else {
if(match(s, i, p, j)){
dp[i][j] = dp[i-1][j-1];
}
}
}
}
return dp[m][n];
}
public boolean match(String s, int i , String p, int j){
if(i < 1){
if(p.charAt(j-1) == '*'){
return true;
}else{
return false;
}
}
if(p.charAt(j-1) == '.'){
return true;
}
return s.charAt(i-1) == p.charAt(j-1);
} |
Beta Was this translation helpful? Give feedback.
-
|
java空间压缩dp版 class Solution {
public boolean isMatch(String s, String p) {
int lenS = s.length(), lenP = p.length();
// 空间压缩
boolean[] cache = new boolean[lenP+1];
// boolean[][] cache = new boolean[lenS+1][lenP+1];
// base case 压缩空间
cache[0] = true;
for (int j=1;j<=lenP;j++) {
char ch = p.charAt(j-1);
if (ch == '*') {
cache[j] = cache[j-2];
}
}
// // base case
// cache[0][0] = true;
// for (int j=1;j<=lenP;j++) {
// char ch = p.charAt(j-1);
// if (ch == '*') {
// cache[0][j] = cache[0][j-2];
// }
// }
// 存放p.charAt(j-2)字符
char prevChP = p.charAt(0);
// 存放cache[i-1][j-1]
boolean prev;
for (int i=1;i<=lenS;i++) {
char chS = s.charAt(i-1);
prev = cache[0];
// base case -> cache[i][0]
cache[0] = i == 0;
for (int j=1;j<=lenP;j++) {
char chP = p.charAt(j-1);
boolean temp = cache[j];
if (chP == '.') {
cache[j] = prev;
// cache[i][j] = cache[i-1][j-1];
} else if (chP == '*') {
if (prevChP == '.' || prevChP == chS) {
cache[j] = cache[j] || cache[j-2];
// cache[i][j] = cache[i-1][j] || cache[i][j-2];
} else {
cache[j] = cache[j-2];
// cache[i][j] = cache[i][j-2];
}
} else {
cache[j] = chS == chP && prev;
// cache[i][j] = chS == chP && cache[i-1][j-1];
}
prevChP = chP;
prev = temp;
}
}
return cache[lenP];
}
} |
Beta Was this translation helpful? Give feedback.
-
|
模式串 ".*" 为啥可以匹配任何文本呢，.是任意字符，*是前面0个或多个，如果.匹配了a，那么.*匹配的不就只能匹配包含a的字符串了吗 |
Beta Was this translation helpful? Give feedback.
-
有一个疑问，希望能解答：可以匹配0到任意多个前面的那一个字符，所以ab可以等价于ab啊，如果ab*可以匹配的话，那么ab可以匹配嘛，如果ab也匹配的话那么第二个base case不就不对了嘛 |
Beta Was this translation helpful? Give feedback.
-
|
想明白了，可以把前面的干掉，如果要匹配空串必须要有才可以，所以我的疑问打消了 |
Beta Was this translation helpful? Give feedback.
-
打卡，并附上Java代码，注释很清楚 //两个字符串的穷举，考虑使用动态规划算法再加两个指针
//使用自顶向下的动态规划，所以使用备忘录来消除重叠子问题
boolean[][] memo;
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
memo = new boolean[n][m];
for (boolean[] booleans : memo) {
Arrays.fill(booleans, false);
}
return dp(s, 0, p, 0);
}
//声明一下dp函数的定义：s[i..]和p[j..]能否匹配
private boolean dp(String s, int i, String p, int j) {
//base case
//1.如果我们p匹配到了最后一个字符，只需要判断此时的i是不是匹配到了s的最后一个字符，如果是的话就匹配成功了，如果不是的话就没有匹配成功
if (j == p.length()) {
return i == s.length();
}
//base case
//2.如果i匹配到了s的最后一个字符，此时我们还要判断j的一个位置，不能简单的判断j是不是匹配到了p的最后一个位置
//因为如果j后面的字符可以匹配一个空串的话也是可以匹配成功的
if (i == s.length()) {
//如果能匹配空串的话，必须字符和*是成对出现的，因为*可以干掉前面的一个字符
if ((p.length() - j) % 2 == 1) {
//不是偶数
return false;
}
//如果是偶数的话，我们还要判断是不是字符和*交替出现
//ab*c*
for (; j + 1 < p.length(); j += 2) {
//如果不是字母和*交替出现直接返回false
if (p.charAt(j + 1) != '*') {
return false;
}
}
return true;
}
if (memo[i][j] != false) {
return memo[i][j];
}
boolean res = false;
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
//如果此时的位置上匹配上了
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
//如果j后面一个字符是*，那么p[j]这个字符可以不匹配，或者匹配一个或者多个
res = dp(s, i + 1, p, j) || dp(s, i, p, j + 2);
} else {
//如果p[j]后面的字符不是*，那么只能老老实实的匹配一个了
res=dp(s,i+1,p,j+1);
}
} else {
//如果此时的位置不能匹配的话
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
//如果此时p[j]后面的字符是*的话，只能不匹配
res = dp(s, i, p, j + 2);
} else {
//如果此时p[j]后面的字符不是*，直接就匹配失败了
return false;
}
}
memo[i][j]=res;
return res;
} |
Beta Was this translation helpful? Give feedback.
-
|
情况1.2时，应该是p[j] 而不是 p[i] |
Beta Was this translation helpful? Give feedback.
and others
-
文章链接点这里：经典动态规划：正则表达式
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions