欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)LeetCode(44.外卡匹配)

 更新時(shí)間:2021年07月12日 10:05:10   作者:Grandyang  
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(44.外卡匹配),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 44. Wildcard Matching 外卡匹配

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

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 = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

這道題通配符外卡匹配問(wèn)題還是小有難度的,有特殊字符 ‘*’ 和 ‘?’,其中 ‘?’ 能代替任何字符,‘*’ 能代替任何字符串,注意跟另一道 Regular Expression Matching 正則匹配的題目區(qū)分開(kāi)來(lái)。兩道題的星號(hào)的作用是不同的,注意對(duì)比區(qū)分一下。這道題最大的難點(diǎn),就是對(duì)于星號(hào)的處理,可以匹配任意字符串,簡(jiǎn)直像開(kāi)了掛一樣,就是說(shuō)在星號(hào)對(duì)應(yīng)位置之前,不管你s中有任何字符串,我大星號(hào)都能匹配你,主角光環(huán)啊。但即便叼如斯的星號(hào),也有其處理不了的問(wèn)題,那就是一旦p中有s中不存在的字符,那么一定無(wú)法匹配,因?yàn)樾翘?hào)只能增加字符,不能消除字符,再有就是星號(hào)一旦確定了要匹配的字符串,對(duì)于星號(hào)位置后面的匹配情況也就鞭長(zhǎng)莫及了。所以p串中星號(hào)的位置很重要,用 jStar 來(lái)表示,還有星號(hào)匹配到s串中的位置,使用 iStart 來(lái)表示,這里 iStar 和 jStar 均初始化為 -1,表示默認(rèn)情況下是沒(méi)有星號(hào)的。然后再用兩個(gè)變量i和j分別指向當(dāng)前s串和p串中遍歷到的位置。

開(kāi)始進(jìn)行匹配,若i小于s串的長(zhǎng)度,進(jìn)行 while 循環(huán)。若當(dāng)前兩個(gè)字符相等,或著p中的字符是問(wèn)號(hào),則i和j分別加1。若 p[j] 是星號(hào),要記錄星號(hào)的位置,jStar 賦為j,此時(shí)j再自增1,iStar 賦為i。若當(dāng)前 p[j] 不是星號(hào),并且不能跟 p[i] 匹配上,此時(shí)就要靠星號(hào)了,若之前星號(hào)沒(méi)出現(xiàn)過(guò),那么就直接跪,比如 s = "aa" 和 p = "c*",此時(shí) s[0] 和 p[0] 無(wú)法匹配,雖然 p[1] 是星號(hào),但還是跪。如果星號(hào)之前出現(xiàn)過(guò),可以強(qiáng)行續(xù)一波命,比如 s = "aa" 和 p = "*c",當(dāng)發(fā)現(xiàn) s[1] 和 p[1] 無(wú)法匹配時(shí),但是好在之前 p[0] 出現(xiàn)了星號(hào),把 s[1] 交給 p[0] 的星號(hào)去匹配。至于如何知道之前有沒(méi)有星號(hào),這時(shí)就能看出 iStar 的作用了,因?yàn)槠涑跏蓟癁?-1,而遇到星號(hào)時(shí),其就會(huì)被更新為i,只要檢測(cè) iStar 的值,就能知道是否可以使用星號(hào)續(xù)命。雖然成功續(xù)了命,匹配完了s中的所有字符,但是之后還要檢查p串,此時(shí)沒(méi)匹配完的p串里只能剩星號(hào),不能有其他的字符,將連續(xù)的星號(hào)過(guò)濾掉,如果j不等于p的長(zhǎng)度,則返回 false,參見(jiàn)代碼如下:

解法一:

class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size();
        while (i < m) {
            if (j < n && (s[i] == p[j] || p[j] == '?')) {
                ++i; ++j;
            } else if (j < n && p[j] == '*') {
                iStar = i;
                jStar = j++;
            } else if (iStar >= 0) {
                i = ++iStar;
                j = jStar + 1;
            } else return false;
        }
        while (j < n && p[j] == '*') ++j;
        return j == n;
    }
};

這道題也能用動(dòng)態(tài)規(guī)劃 Dynamic Programming 來(lái)解,寫(xiě)法跟之前那道題 Regular Expression Matching 很像,但是還是不一樣。外卡匹配和正則匹配最大的區(qū)別就是在星號(hào)的使用規(guī)則上,對(duì)于正則匹配來(lái)說(shuō),星號(hào)不能單獨(dú)存在,前面必須要有一個(gè)字符,而星號(hào)存在的意義就是表明前面這個(gè)字符的個(gè)數(shù)可以是任意個(gè),包括0個(gè),那么就是說(shuō)即使前面這個(gè)字符并沒(méi)有在s中出現(xiàn)過(guò)也無(wú)所謂,只要后面的能匹配上就可以了。而外卡匹配就不是這樣的,外卡匹配中的星號(hào)跟前面的字符沒(méi)有半毛錢(qián)關(guān)系,如果前面的字符沒(méi)有匹配上,那么直接返回 false 了,根本不用管星號(hào)。而星號(hào)存在的作用是可以表示任意的字符串,當(dāng)然只是當(dāng)匹配字符串缺少一些字符的時(shí)候起作用,當(dāng)匹配字符串p包含目標(biāo)字符串s中沒(méi)有的字符時(shí),將無(wú)法成功匹配。

對(duì)于這種玩字符串的題目,動(dòng)態(tài)規(guī)劃 Dynamic Programming 是一大神器,因?yàn)樽址渥哟g的關(guān)系十分密切,正好適合 DP 這種靠推導(dǎo)狀態(tài)轉(zhuǎn)移方程的特性。那么先來(lái)定義dp數(shù)組吧,使用一個(gè)二維 dp 數(shù)組,其中 dp[i][j] 表示 s中前i個(gè)字符組成的子串和p中前j個(gè)字符組成的子串是否能匹配。大小初始化為 (m+1) x (n+1),加1的原因是要包含 dp[0][0] 的情況,因?yàn)槿魋和p都為空的話(huà),也應(yīng)該返回 true,所以也要初始化 dp[0][0] 為 true。還需要提前處理的一種情況是,當(dāng)s為空,p為連續(xù)的星號(hào)時(shí)的情況。由于星號(hào)是可以代表空串的,所以只要s為空,那么連續(xù)的星號(hào)的位置都應(yīng)該為 true,所以先將連續(xù)星號(hào)的位置都賦為 true。然后就是推導(dǎo)一般的狀態(tài)轉(zhuǎn)移方程了,如何更新 dp[i][j],首先處理比較 tricky 的情況,若p中第j個(gè)字符是星號(hào),由于星號(hào)可以匹配空串,所以如果p中的前 j-1 個(gè)字符跟s中前i個(gè)字符匹配成功了( dp[i][j-1] 為true)的話(huà),則 dp[i][j] 也能為 true。或者若p中的前j個(gè)字符跟s中的前i-1個(gè)字符匹配成功了( dp[i-1][j] 為true )的話(huà),則 dp[i][j] 也能為 true(因?yàn)樾翘?hào)可以匹配任意字符串,再多加一個(gè)任意字符也沒(méi)問(wèn)題)。若p中的第j個(gè)字符不是星號(hào),對(duì)于一般情況,假設(shè)已經(jīng)知道了s中前 i-1 個(gè)字符和p中前 j-1 個(gè)字符的匹配情況(即 dp[i-1][j-1] ),現(xiàn)在只需要匹配s中的第i個(gè)字符跟p中的第j個(gè)字符,若二者相等( s[i-1] == p[j-1] ),或者p中的第j個(gè)字符是問(wèn)號(hào)( p[j-1] == '?' ),再與上 dp[i-1][j-1] 的值,就可以更新 dp[i][j] 了,參見(jiàn)代碼如下:

解法二:

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p[i - 1] == '*') dp[0][i] = dp[0][i - 1];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

其實(shí)這道題也可以使用遞歸來(lái)做,因?yàn)樽哟蛘咦訑?shù)組這種形式,天然適合利用遞歸來(lái)做。但是愣了吧唧的遞歸跟暴力搜索并沒(méi)有啥太大的區(qū)別,很容易被 OJ 斃掉,比如評(píng)論區(qū)六樓的那個(gè) naive 的遞歸,其實(shí)完全是按照題目要求來(lái)的。首先判斷s串,若為空,那么再看p串,若p為空,則為 true,或者跳過(guò)星號(hào),繼續(xù)調(diào)用遞歸。若s串不為空,且p串為空,則直接 false。若s串和p串均不為空,進(jìn)行第一個(gè)字符的匹配,若相等,或者 p[0] 是問(wèn)號(hào),則跳過(guò)首字符,對(duì)后面的子串調(diào)用遞歸。若 p[0] 是星號(hào),先嘗試跳過(guò)s串的首字符,調(diào)用遞歸,若遞歸返回 true,則當(dāng)前返回 true。否則嘗試跳過(guò)p串的首字符,調(diào)用遞歸,若遞歸返回 true,則當(dāng)前返回 true。但是很不幸,內(nèi)存超出限制了 MLE,那么博主做了個(gè)簡(jiǎn)單的優(yōu)化,跳過(guò)了連續(xù)的星號(hào),參見(jiàn)評(píng)論區(qū)七樓的代碼,但是這次時(shí)間超出了限制 TLE。博主想是不是取子串 substr() 操作太費(fèi)時(shí)間,且調(diào)用遞歸的適合s串和p串又分別建立了副本,才導(dǎo)致的 TLE。于是想著用坐標(biāo)變量來(lái)代替取子串,并且遞歸函數(shù)調(diào)用的s串和p串都加上引用,代碼參見(jiàn)評(píng)論區(qū)八樓,但還是跪了,OJ 大佬,刀下留人啊。最后還是在論壇上找到了一個(gè)使用了神奇的剪枝的方法,這種解法的遞歸函數(shù)返回類(lèi)型不是 bool 型,而是整型,有三種不同的狀態(tài),返回0表示匹配到了s串的末尾,但是未匹配成功;返回1表示未匹配到s串的末尾就失敗了;返回2表示成功匹配。那么只有返回值大于1,才表示成功匹配。至于為何失敗的情況要分類(lèi),就是為了進(jìn)行剪枝。在遞歸函數(shù)中,若s串和p串都匹配完成了,返回狀態(tài)2。若s串匹配完成了,但p串但當(dāng)前字符不是星號(hào),返回狀態(tài)0。若s串未匹配完,p串匹配完了,返回狀態(tài)1。若s串和p串均為匹配完,且當(dāng)前字符成功匹配的話(huà),對(duì)下一個(gè)位置調(diào)用遞歸。否則若p串當(dāng)前字符是星號(hào),首先跳過(guò)連續(xù)的星號(hào)。然后分別讓星號(hào)匹配空串,一個(gè)字符,兩個(gè)字符,....,直到匹配完整個(gè)s串,對(duì)每種情況分別調(diào)用遞歸函數(shù),接下來(lái)就是最大的亮點(diǎn)了,也是最有用的剪枝,當(dāng)前返回值為狀態(tài)0或者2的時(shí)候,返回,否則繼續(xù)遍歷。如果僅僅是狀態(tài)2的時(shí)候才返回,就像評(píng)論區(qū)八樓的代碼,會(huì)有大量的重復(fù)計(jì)算,因?yàn)楫?dāng)返回值為狀態(tài)0的時(shí)候,已經(jīng)沒(méi)有繼續(xù)循環(huán)下去的必要了,非常重要的一刀剪枝,參見(jiàn)代碼如下:

解法三:

class Solution {
public:
    bool isMatch(string s, string p) {
        return helper(s, p, 0, 0) > 1;
    }
    int helper(string& s, string& p, int i, int j) {
        if (i == s.size() && j == p.size()) return 2;
        if (i == s.size() && p[j] != '*') return 0;
        if (j == p.size()) return 1;
        if (s[i] == p[j] || p[j] == '?') {
            return helper(s, p, i + 1, j + 1);
        }
        if (p[j] == '*') {
            if (j + 1 < p.size() && p[j + 1] == '*') {
                return helper(s, p, i, j + 1);
            }
            for (int k = 0; k <= (int)s.size() - i; ++k) {
                int res = helper(s, p, i + k, j + 1);
                if (res == 0 || res == 2) return res;
            }
        }
        return 1;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(44.外卡匹配)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)外卡匹配內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C++中 string 中的常用方法使用心得

    C++中 string 中的常用方法使用心得

    這篇文章主要介紹了C++中 string 中的常用方法使用心得,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-03-03
  • C++實(shí)現(xiàn)一個(gè)簡(jiǎn)單消息隊(duì)列的示例詳解

    C++實(shí)現(xiàn)一個(gè)簡(jiǎn)單消息隊(duì)列的示例詳解

    消息隊(duì)列在多線(xiàn)程的場(chǎng)景有時(shí)會(huì)用到,尤其是線(xiàn)程通信跨線(xiàn)程調(diào)用的時(shí)候,就可以使用消息隊(duì)列進(jìn)行通信。本文將利用C++實(shí)現(xiàn)一個(gè)簡(jiǎn)單的消息隊(duì)列,感興趣的可以了解一下
    2022-12-12
  • CLOSE_WAIT狀態(tài)解決方案

    CLOSE_WAIT狀態(tài)解決方案

    這篇文章主要介紹了CLOSE_WAIT狀態(tài)解決方案,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • 在C++程序中開(kāi)啟和禁用Windows設(shè)備的無(wú)線(xiàn)網(wǎng)卡的方法

    在C++程序中開(kāi)啟和禁用Windows設(shè)備的無(wú)線(xiàn)網(wǎng)卡的方法

    這篇文章主要介紹了在C++程序中開(kāi)啟和禁用Windows設(shè)備的無(wú)線(xiàn)網(wǎng)卡的方法,包括一些常見(jiàn)錯(cuò)誤的分析與解決,需要的朋友可以參考下
    2016-03-03
  • C/C++中如何判斷某一文件或目錄是否存在

    C/C++中如何判斷某一文件或目錄是否存在

    以下文章是對(duì)C/C++中判斷某一文件或目錄是否存在的實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以參考下
    2013-07-07
  • 使用UDP協(xié)議實(shí)現(xiàn)單詞翻譯服務(wù)器

    使用UDP協(xié)議實(shí)現(xiàn)單詞翻譯服務(wù)器

    這篇文章主要為大家詳細(xì)介紹了如何使用UDP協(xié)議實(shí)現(xiàn)英文單詞翻譯服務(wù)器,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價(jià)值,感興趣的小伙伴可以了解下
    2023-08-08
  • C++進(jìn)程鏈接工具之通信器詳解

    C++進(jìn)程鏈接工具之通信器詳解

    本文主要介紹了C++通信器的示例代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2022-11-11
  • C語(yǔ)言之選擇分支語(yǔ)句詳解

    C語(yǔ)言之選擇分支語(yǔ)句詳解

    大家好,本篇文章主要講的是C語(yǔ)言之選擇分支語(yǔ)句詳解,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話(huà)記得收藏一下,方便下次瀏覽
    2021-12-12
  • C++中replace()函數(shù)使用方法匯總

    C++中replace()函數(shù)使用方法匯總

    這篇文章主要介紹了C++中replace()函數(shù)使用方法匯總,在這篇文章中為大家詳細(xì)介紹C++ replace()函數(shù)的各種應(yīng)用方式,希望朋友們可以從這里介紹的內(nèi)容充分掌握這一應(yīng)用技巧
    2015-11-11
  • Qt實(shí)現(xiàn)UI界面純代碼示例

    Qt實(shí)現(xiàn)UI界面純代碼示例

    這篇文章主要給大家介紹了關(guān)于Qt實(shí)現(xiàn)UI界面的相關(guān)資料,使用Qt純代碼,實(shí)現(xiàn)了基本的界面,對(duì)大家學(xué)習(xí)或者使用Qt具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2024-01-01

最新評(píng)論