lemon-blog
所有文章 标签 分类 文档 关于
lemon-blog

目录

leetcode10.正则表达式匹配

 收录于 leetcode
   约 1718 字   预计阅读 4 分钟 
/leetcode10.%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F%E5%8C%B9%E9%85%8D/featured-image.png

简介：正则表达式 dp hard

2 动态规划设计

2.10 正则表达式

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

  • ‘.’ 匹配任意单个字符
  • ‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

1
2
3

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

1
2
3

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

1
2
3

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

解法一

暴力递归 击败了10.78%的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    public boolean isMatch(String s, String p) {
        return dp(s, 0, p, 0);
    }

    public boolean dp(String s, int i, String p, int j) {
        //递归出口
        if(j == p.length()) {
            return i == s.length();
        }
        if(i == s.length()) {
            if((p.length() - j) % 2 != 0) {
                return false;
            }
            for(; j+1 < p.length(); j += 2) {
                if(p.charAt(j+1) != '*') {
                    return false;
                }
            }
            return true;
        }
        
        //递归
        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
            //匹配
            if(j < p.length() - 1 && p.charAt(j+1) == '*') {
                //通配符匹配 0次或者多次
                return dp(s, i, p, j+2) || dp(s, i+1, p, j);
            } else {
                //普通字符匹配
                return dp(s, i+1, p, j+1);
            }
        } else {
            //未匹配
            if(j < p.length() - 1 && p.charAt(j+1) == '*') {
                //通配符匹配 0次
                return dp(s, i, p, j+2);
            } else {
                //普通字符匹配
                return false;
            }
        }
    }
}

解法二

自上而下 记忆化搜索 击败了16.52%的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class Solution {
    public Map<String, Boolean> map;

    public boolean isMatch(String s, String p) {
        map = new HashMap<String, Boolean>();
        return dp(s, 0, p, 0);
    }

    public String key(int i, int j) {
        return Integer.toString(i) + "," + Integer.toString(j);
    }

    public boolean dp(String s, int i, String p, int j) {
        //递归出口
        if(map.containsKey(key(i, j))) return map.get(key(i, j));
        boolean res;
        if(j == p.length()) {
            res = (i == s.length());
            map.put(key(i, j), res);
            return res; 
        }
        if(i == s.length()) {
            if((p.length() - j) % 2 != 0) {
                res = false;
                map.put(key(i, j), res);
                return res; 
            }
            for(; j+1 < p.length(); j += 2) {
                if(p.charAt(j+1) != '*') {
                    res = false;
                    map.put(key(i, j), res);
                    return res; 
                }
            }
            res = true;
            map.put(key(i, j), res);
            return res; 
        }
        
        //递归
        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
            //匹配
            if(j < p.length() - 1 && p.charAt(j+1) == '*') {
                //通配符匹配 0次或者多次
                res = dp(s, i, p, j+2) || dp(s, i+1, p, j);
                map.put(key(i, j), res);
            } else {
                //普通字符匹配
                res = dp(s, i+1, p, j+1);
                map.put(key(i, j), res);
            }
        } else {
            //未匹配
            if(j < p.length() - 1 && p.charAt(j+1) == '*') {
                //通配符匹配 0次
                res = dp(s, i, p, j+2);
                map.put(key(i, j), res);
            } else {
                //普通字符匹配
                res = false;
                map.put(key(i, j), res);
            }
        }
        return res; 
    }
}

解法三

自下而上 动态规划 击败了100%的用户

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
    public boolean isMatch(String s, String p) {
        int n1 = s.length();
        int n2 = p.length();
        //dp
        //定义dp数组：dp[i][j]代表s[i ~ n1 - 1]和p[j ~ n2 - 1]是否能匹配
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        //base case
        dp[n1][n2] = true;
        for(int j = n2 - 1; j >= 0; j -= 2) {
            if(p.charAt(j) == '*') {
                dp[n1][j - 1] = true;
            } else {
                break;
            }
        }
        //状态转移方程
        for(int i = n1 - 1; i >= 0; i--) {
            for(int j = n2 - 1; j >= 0; j--) {
                if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                    //匹配
                    if(j < n2 - 1 && p.charAt(j+1) == '*') {
                        //通配符匹配 0次或者多次
                        dp[i][j] = dp[i][j+2] || dp[i+1][j];
                    } else {
                        //普通字符匹配
                        dp[i][j] = dp[i+1][j+1];
                    }
                } else {
                    //未匹配
                    if(j < n2 - 1 && p.charAt(j+1) == '*') {
                        //通配符匹配 0次
                        dp[i][j] = dp[i][j+2];
                    } else {
                        //普通字符匹配
                        dp[i][j] = false;
                    }
                }
            }
        }
        //返回值
        return dp[0][0];
    }
}

解法四

不难发现：dp[i][j]仅仅与dp[i+1][j+1],dp[i][j+2],dp[i+1][j]的状态有关，所以可以进行状态压缩，减小空间复杂度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution {
    public boolean isMatch(String s, String p) {
        int n1 = s.length();
        int n2 = p.length();
        //dp
        //定义dp数组：dp[j]代表s[i ~ n1 - 1]和p[j ~ n2 - 1]是否能匹配
        boolean[] dp = new boolean[n2 + 1];
        boolean[] pre = new boolean[n2 + 1];
        //base case
        pre[n2] = true;
        for(int j = n2 - 1; j >= 0; j -= 2) {
            if(p.charAt(j) == '*') {
                pre[j-1] = true;
            } else {
                break;
            }
        }
        //状态转移方程
        for(int i = n1 - 1; i >= 0; i--) {
            for(int j = n2 - 1; j >= 0; j--) {
                if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                    //匹配
                    if(j < n2 - 1 && p.charAt(j+1) == '*') {
                        //通配符匹配 0次或者多次
                        dp[j] = dp[j+2] || pre[j];
                    } else {
                        //普通字符匹配
                        dp[j] = pre[j+1];
                    }
                } else {
                    //未匹配
                    if(j < n2 - 1 && p.charAt(j+1) == '*') {
                        //通配符匹配 0次
                        dp[j] = dp[j+2];
                    } else {
                        //普通字符匹配
                        dp[j] = false;
                    }
                }
            }
            pre = Arrays.copyOf(dp, n2 + 1);
        }
        //返回值
        return dp[0];
    }
}
更新于 2023-04-24
阅读原始文档
 java, leetcode
返回 | 主页