国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Regular Expression Matching 正則表達式匹配

Vixb / 3468人閱讀

摘要：為的條件是為，且第個字符也能被成功匹配。而從后往前匹配則不會影響該星號后面星號所匹配的部分，因為已經匹配的部分我們會直接跳過。這樣才能防止最后字母沒有匹配上，而前面的部分反而把的結尾給匹配了。

Regular Expression Matching 
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).


The function prototype should be:


bool isMatch(const char *s, const char *p)



Some examples:


isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
動態規劃 復雜度

時間 O(NM) 空間 O(N)

思路

這道題可以用遞歸解決，不過時間復雜度是指數級，這里介紹一個用動態規劃在平方時間內解決的辦法。
解法的核心理念是：從后往前看pattern的每一位，對于pattern的每一位，我們盡可能的把待匹配串string從后往前給匹配上。我們用一個數組match[string.length() + 1]來表示string被匹配的情況，這里如果match[j]是true，而我們pattern正指向第i位，則說明string從第j位到最后都已經被pattern第i位之前的某些部分給成功匹配了，所以我們不用再操心了。match[i]為true的條件是match[i + 1]為true，且string第i個字符也能被成功匹配。

那我們就可以從后往前開始看pattern的每一位能匹配多少string的字符了：

如果pattern的這一位是*，那我們要用這一位，來從后往前嘗試匹配string，因為string后面是已經匹配好的，前面是還沒匹配好的，所以從前往后匹配星號可能會導致我們匹配了一些pattern該星號前面的星號應該匹配的部分。而從后往前匹配則不會影響pattern該星號后面星號所匹配的部分，因為已經匹配的部分我們會直接跳過。

如果pattern這一位不是*，那我們則不能匹配多個字符，我們只能匹配一個字符，這時候要對string從前往后匹配，因為如果后面沒被匹配，前面也肯定不會被匹配，所以從前向后能保證我們把pattern的這一位匹配到string當前最后面那個還沒匹配的字符。這樣如果那個字符能被匹配就通過了。

我們舉個例子

match:   0 0 0 1
string:  a a b
pattern: a * b
             |

這里我們先看pattern最后一位b能匹配到多少，這里因為b不是星號，所以我們從左往右嘗試匹配string，第一個a不行，第二個a也不行，然后到b，這里因為match[3]是true，b也和b相同，所以匹配成功。

match:   0 0 1 1
string:  a a b
pattern: a * b
           |

然后看pattern的這個星號，我們要從后往前匹配string。因為b已經被匹配了，match[2]是true，所以直接跳過。然后到a，發現個pattern中星號前面的字符a相同，所以匹配成功，match[1]也置為true再看string的第一個a，還是可以匹配成功，這樣整個string都被匹配成功了。

這里還有幾個情況，首先，無論剛才那pattern中最后一個b有沒有匹配到string中任何一個字符，match[3]也要置為false。這樣才能防止pattern最后字母沒有匹配上，而pattern前面的部分反而把string的結尾給匹配了。還有如果pattern中是句號的話，那相當于字符相同。

代碼 
public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[] match = new boolean[s.length() + 1];
        match[s.length()] = true;
        for(int i = p.length() - 1; i >=0; i--){
            if(p.charAt(i) == "*"){
                // 如果是星號，從后往前匹配
                for(int j = s.length() - 1; j >= 0; j--){
                    match[j] = match[j] || (match[j + 1] && (p.charAt(i - 1) == "." || (p.charAt(i - 1) == s.charAt(j)))); 
                }
                // 記得把i多減一，因為星號是和其前面的字符配合使用的
                i--;
            } else {
                // 如果不是星號，從前往后匹配
                for(int j = 0; j < s.length(); j++){
                    match[j] = match[j + 1] && (p.charAt(i) == "." || (p.charAt(i) == s.charAt(j)));
                }
                // 只要試過了pattern中最后一個字符，就要把match[s.length()]置為false
                match[s.length()] = false;
            }
        }
        return match[0];
    }
}

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64725.html

相關文章

  • Leetcode 10 Regular Expression Matching 簡單正則匹配

    摘要：難度這道題要求我們實現簡單的正則表達式的匹配只要求普通字符的匹配了解正則的同學都清楚代表任意單個字符代表個或多個前面的字符比如可以匹配到空字符串也可以匹配等等題目還要求我們判定正則是否匹配給定的字符串要判定整個字符串而不是其中一部分匹配就算 Implement regular expression matching with support for . and *. . Matche...

    OnlyLing 評論0 收藏0

  • 手動實現.*正則表達式匹配函數

    摘要：手動實現正則表達式匹配函數思路使用迭代，當每次判斷后令當時特殊處理，注意可以代表到多個之前一個的字符當時，循環判斷代表多少個之前一個的字符，如果可以匹配之后的模式，返回，否則注意處理邊界值的情況，和為空串時代碼可以代表一到多次本題以及其它題 手動實現.*正則表達式匹配函數 regular expression matching . Matches any single charact...

    muddyway 評論0 收藏0

  • [LeetCode] 10. Regular Expression Matching

    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. Th...

    mo0n1andin 評論0 收藏0

  • Python中fnmatch模塊的使用

    摘要：函數匹配能力介于簡單的字符串方法和強大的正則表達式之間，如果在數據處理操作中只需要簡單的通配符就能完成的時候，這通常是一個比較合理的方案。此模塊的主要作用是文件名稱的匹配，并且匹配的模式使用的風格。 fnmatch()函數匹配能力介于簡單的字符串方法和強大的正則表達式之間，如果在數據處理操作中只需要簡單的通配符就能完成的時候，這通常是一個比較合理的方案。此模塊的主要作用是文件名稱的匹配...

    PAMPANG 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<