一、通配符匹配

題目描述：

給你一個輸入字符串 (s) 和一個字符模式 § ，請你實現(xiàn)一個支持 ‘?’ 和 ‘*’ 匹配規(guī)則的通配符匹配：

• ‘?’ 可以匹配任何單個字符。
• ‘*’ 可以匹配任意字符序列（包括空字符序列）。
  判定匹配成功的充要條件是：字符模式必須能夠 完全匹配 輸入字符串（而不是部分匹配）。

示例 1：

輸入：s = “aa”, p = “a”
輸出：false
解釋：“a” 無法匹配 “aa” 整個字符串。

示例 2：

輸入：s = “aa”, p = ""
輸出：true
解釋：'’ 可以匹配任意字符串。

示例 3：

輸入：s = “cb”, p = “?a”
輸出：false
解釋：‘?’ 可以匹配 ‘c’, 但第二個 ‘a’ 無法匹配 ‘b’。

1.1 思路分析

我們可以分別以i和j表示s[0~i]和p[0~j]是否能成功匹配。

那么這里就只用討論i和j的位置，有四種情況：
1?? 如果s[i] == p[j]，那么我們就只用判斷dp[i - 1][j - 1]是否能成功匹配，如果能成功匹配，那么說明加上i和j的位置也能成功匹配。
狀態(tài)轉移方程：dp[i][j] = s[i] == p[j] && dp[i - 1][j - 1]
2?? 如果p[j] == '?'那么說明此時s[i]不管是什么都可以，只需要判斷dp[i - 1][j - 1]是否能成功匹配，就跟上面一樣。
狀態(tài)轉移方程：dp[i][j] = p[j] == '?' && dp[i - 1][j - 1]
3?? 如果p[j] == '*'，這里的情況就比較多，因為它可以變成0個或多個字符：

這么多情況只要有一種情況滿足條件即可。

狀態(tài)轉移方程：

for(int k = 0; k <= i; k++)
{
    if(dp[i - k][j - 1])
    {
        dp[i][j] = true;
        break;
    }
}

4?? 如果p[j] != '?' && p[j] != '*' && p[j] != s[i]，那么說明不能匹配。

1.2 初始化處理

我們看到狀態(tài)轉移方程會用到i-1和j- 1，所以dp表可以多開一維，而為了不改變下標的映射關系，我們可以在s串和p串的開頭各自添加一個字符。
接下來就是初始化，首先dp[0][0]就代表兩個空串，一定能匹配。所以dp[0][0] = true;
其次還有*在p串開頭的位置出現(xiàn)，因為*可以變成空串，所以只要是開頭的*都可以跟s[0]匹配成功：dp[0][j] = true;

1.3 代碼

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

1.4 優(yōu)化

p[j] == '*'這種情況其實可以寫成：

而經過觀察可以再寫出一個式子：

經過觀察可以發(fā)現(xiàn)藍色框框圈起來的部分是相等的

所以可以寫成：

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

二、正則表達式匹配

題目描述：

給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 ‘.’ 和 ‘*’ 的正則表達式匹配。

• ‘.’ 匹配任意單個字符
• ‘*’ 匹配零個或多個前面的那一個元素
  所謂匹配，是要涵蓋 整個 字符串 s的，而不是部分字符串。

示例 1：

輸入：s = “aa”, p = “a”
輸出：false
解釋：“a” 無法匹配 “aa” 整個字符串。

示例 2:

輸入：s = “aa”, p = “a*”
輸出：true
解釋：因為 ‘*’ 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 ‘a’。因此，字符串 “aa” 可被視為 ‘a’ 重復了一次。

示例 3：

輸入：s = “ab”, p = “."
輸出：true
解釋：".” 表示可匹配零個或多個（‘*’）任意字符（‘.’）。

這里的.字符跟上面一道題的?作用是一樣的。但是*字符又區(qū)別，它的作用是把*字符的前一個字符重復0次或者多次，比方說"a*"
它可以變成："","a","aa","aaa"……

2.1 思路分析

這里的有些情況跟上面的重復：
當dp[i - 1][j - 1] && (p[j] == '.' || s[i] == p[j])的時候，dp[i][j]=true。
接下來只剩p[j] == '*' 的情況：
這里要分情況討論j的前一個元素，如果前一個元素是.，那么也就是可以變成任意的多個字符，既然要匹配多個字符，那么又是跟上面一個題一樣要討論到底變成多長。因為上面講過優(yōu)化版，所以這里直接寫：

接下來如果前面一個字符是普通字符：

這里解釋以下：空自然不用說，當只變成長度為1的字符串時，首先要判斷j的前一個字符是否等于s[i]，如果不相等就不用考慮前面的了。

2.2 初始化設置

還是跟上面一樣多加一維，然后讓dp[0][0] = true，接下來就是看p的前面全部是x*x*……這種字符串的情況：文章來源地址http://www.zghlxwxcb.cn/news/detail-470521.html

for(int j = 2; j < m; j += 2)
{
    if(p[j] == '*') dp[0][j] = true;
    else break;
}

2.3 代碼

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

到了這里，關于【動態(tài)規(guī)劃】通配符匹配與正則表達式匹配的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！