[LeetCode] 10. Regular Expression Matching

mo0n1andin 发布于2019-08-16 13:28 / 546人阅读

Problem

Given an input string (s) and a pattern (p), implement regular expression matching with support for "." and "*".

"." Matches any single character.
"*" Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: "*" means zero or more of the precedeng element, "a". Therefore, by repeating "a" once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solution

class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) return false;
        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) == "*" && dp[0][i-1]) dp[0][i+1] = true;
        }
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                // "." or same char
                if (p.charAt(j) == "." || p.charAt(j) == s.charAt(i)) {
                    dp[i+1][j+1] = dp[i][j];
                } else if (j != 0 && p.charAt(j) == "*") {
                    if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != ".") {
                        dp[i+1][j+1] = dp[i+1][j-1];
                    } else {
                        //multiple s.charAt(i) or none s.charAt(i)
                        dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j-1]; 
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}

云服务器 GPU云服务器 regular_expression regular-expression matching regular

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71801.html

[Leetcode] Regular Expression Matching 正则表达式匹配

摘要：为的条件是为，且第个字符也能被成功匹配。而从后往前匹配则不会影响该星号后面星号所匹配的部分，因为已经匹配的部分我们会直接跳过。这样才能防止最后字母没有匹配上，而前面的部分反而把的结尾给匹配了。 Regular Expression Matching Implement regular expression matching with support for . and*. . Mat...

Vixb 2019-08-14 12:49 评论0 收藏0
Leetcode 10 Regular Expression Matching 简单正则匹配

摘要：难度这道题要求我们实现简单的正则表达式的匹配只要求普通字符的匹配了解正则的同学都清楚代表任意单个字符代表个或多个前面的字符比如可以匹配到空字符串也可以匹配等等题目还要求我们判定正则是否匹配给定的字符串要判定整个字符串而不是其中一部分匹配就算 Implement regular expression matching with support for . and *. . Matche...

OnlyLing 2019-08-14 17:14 评论0 收藏0
10 Regular Expression Matching，填dp table

摘要：解释清楚这两个条件是如何推导的。表示维持原位置，位置的，和位置的一同消失。 Implement regular expression matching with support for . and *. . Matches any single character. * Matches zero or more of the preceding element. The matchi...

MingjunYang 2019-08-14 17:59 评论0 收藏0
Wildcard Matching

摘要：题目链接这道题还是可以用的方法，用的数组来解，空间复杂度较高。和不同，这道题的符号和前面的没有关系，不需要一起考虑。最坏的情况下，间隔出现且每个都要匹配很多字符，设一个平均匹配里面个字符，。其中，是的长度，是的长度。 Wildcard Matching 题目链接：https://leetcode.com/problems...这道题还是可以用Regular Expression Mat...

galaxy_robot 2019-08-14 17:19 评论0 收藏0
手动实现.*正则表达式匹配函数

摘要：手动实现正则表达式匹配函数思路使用迭代，当每次判断后令当时特殊处理，注意可以代表到多个之前一个的字符当时，循环判断代表多少个之前一个的字符，如果可以匹配之后的模式，返回，否则注意处理边界值的情况，和为空串时代码可以代表一到多次本题以及其它题手动实现.*正则表达式匹配函数 regular expression matching . Matches any single charact...

muddyway 2019-07-25 12:02 评论0 收藏0