成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Regular Expression Matching 正則表達(dá)式匹配

Vixb / 3474人閱讀

摘要：為的條件是為，且第個(gè)字符也能被成功匹配。而從后往前匹配則不會(huì)影響該星號(hào)后面星號(hào)所匹配的部分，因?yàn)橐呀?jīng)匹配的部分我們會(huì)直接跳過。這樣才能防止最后字母沒有匹配上，而前面的部分反而把的結(jié)尾給匹配了。

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
動(dòng)態(tài)規(guī)劃 復(fù)雜度

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

思路

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

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

如果pattern的這一位是*，那我們要用這一位，來從后往前嘗試匹配string，因?yàn)閟tring后面是已經(jīng)匹配好的，前面是還沒匹配好的，所以從前往后匹配星號(hào)可能會(huì)導(dǎo)致我們匹配了一些pattern該星號(hào)前面的星號(hào)應(yīng)該匹配的部分。而從后往前匹配則不會(huì)影響pattern該星號(hào)后面星號(hào)所匹配的部分，因?yàn)橐呀?jīng)匹配的部分我們會(huì)直接跳過。

如果pattern這一位不是*，那我們則不能匹配多個(gè)字符，我們只能匹配一個(gè)字符，這時(shí)候要對(duì)string從前往后匹配，因?yàn)槿绻竺鏇]被匹配，前面也肯定不會(huì)被匹配，所以從前向后能保證我們把pattern的這一位匹配到string當(dāng)前最后面那個(gè)還沒匹配的字符。這樣如果那個(gè)字符能被匹配就通過了。

我們舉個(gè)例子

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

這里我們先看pattern最后一位b能匹配到多少，這里因?yàn)閎不是星號(hào)，所以我們從左往右嘗試匹配string，第一個(gè)a不行，第二個(gè)a也不行，然后到b，這里因?yàn)?b>match[3]是true，b也和b相同，所以匹配成功。

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

然后看pattern的這個(gè)星號(hào)，我們要從后往前匹配string。因?yàn)閎已經(jīng)被匹配了，match[2]是true，所以直接跳過。然后到a，發(fā)現(xiàn)個(gè)pattern中星號(hào)前面的字符a相同，所以匹配成功，match[1]也置為true再看string的第一個(gè)a，還是可以匹配成功，這樣整個(gè)string都被匹配成功了。

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

代碼 
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) == "*"){
                // 如果是星號(hào)，從后往前匹配
                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多減一，因?yàn)樾翘?hào)是和其前面的字符配合使用的
                i--;
            } else {
                // 如果不是星號(hào)，從前往后匹配
                for(int j = 0; j < s.length(); j++){
                    match[j] = match[j + 1] && (p.charAt(i) == "." || (p.charAt(i) == s.charAt(j)));
                }
                // 只要試過了pattern中最后一個(gè)字符，就要把match[s.length()]置為false
                match[s.length()] = false;
            }
        }
        return match[0];
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64725.html

相關(guān)文章

  • Leetcode 10 Regular Expression Matching 簡(jiǎn)單正則匹配

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

    OnlyLing 評(píng)論0 收藏0

  • 手動(dòng)實(shí)現(xiàn).*正則表達(dá)式匹配函數(shù)

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

    muddyway 評(píng)論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 評(píng)論0 收藏0

  • Python中fnmatch模塊的使用

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

    PAMPANG 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<