[LeetCode] 10. Regular Expression Matching

mo0n1andin 發布于2019-08-16 13:28 / 569人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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