leetcode-44. Wildcard Matching

leanxi 發(fā)布于2019-07-30 17:20 / 1473人閱讀

摘要：正則由于的存在，所以有多種狀態(tài)，中間狀態(tài)儲(chǔ)存都需要記錄下來(lái)。然后以這些狀態(tài)為動(dòng)態(tài)的中轉(zhuǎn)，繼續(xù)判斷到最后。最后正則匹配字符串是否成功的判斷依據(jù)，就是正則字符串的最大，是否出現(xiàn)在遍歷到最后的狀態(tài)列表中。

題目闡釋：

正則匹配字符串，用程序?qū)崿F(xiàn)

關(guān)鍵理解：

正則匹配，動(dòng)態(tài)規(guī)劃思想，一個(gè)個(gè)向后追溯，后面的依賴前面的匹配成功。
正則和待匹配的字符串長(zhǎng)度不一，統(tǒng)一到正則字符串的index索引上，每次的字符串index移動(dòng)，都以匹配到的正則的index為準(zhǔn)。
正則由于*?的存在，所以有多種狀態(tài)，中間狀態(tài)儲(chǔ)存都需要記錄下來(lái)。然后以這些狀態(tài)為動(dòng)態(tài)的中轉(zhuǎn)，繼續(xù)判斷到最后。
最后正則匹配字符串是否成功的判斷依據(jù)，就是正則字符串的最大index，是否出現(xiàn)在遍歷到最后的狀態(tài)列表中。

錯(cuò)誤之處：

多處動(dòng)態(tài)變化，導(dǎo)致無(wú)法入手，*沒有處理思路，沒有找到匹配成功的條件

應(yīng)用：

正則屬于多條路徑問題，可以推理到 多種渠道的問題，匹配成功當(dāng)前的才往后推
*相當(dāng)于無(wú)限向后匹配，所以無(wú)限循環(huán)使用，看能否匹配成功。

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

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        transfer = {}
        index=0
        for char in p:
            if char=="*":
                transfer[index,char]=index
            else:
                transfer[index,char]=index+1
                index+=1
        accept=index

        # index=0
        state = {0}
        for char in s:
            state_tmp=set()
            for index in state:
                for char_prob in [char,"?","*"]:
                    index_next=transfer.get((index,char_prob))
                    state_tmp.add(index_next)
            state=state_tmp
        return accept in state


if __name__=="__main__":
    s = "acdcb"
    p = "a*c?b"
    p = "a**c?d"
    st=Solution()
    out=st.isMatch(s,p)
    print(out)