fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
经典动态规划：正则表达式 :: labuladong的算法小抄
补充一下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]
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];
}
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;
}
}
迭代+空间压缩
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];
}
}
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];
}
}
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]
}
楼上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;
}
}`
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]
}
