資訊專欄INFORMATION COLUMN
摘要：正則由于的存在，所以有多種狀態(tài)，中間狀態(tài)儲存都需要記錄下來。然后以這些狀態(tài)為動態(tài)的中轉(zhuǎn)，繼續(xù)判斷到最后。最后正則匹配字符串是否成功的判斷依據(jù)，就是正則字符串的最大，是否出現(xiàn)在遍歷到最后的狀態(tài)列表中。
題目闡釋：
正則匹配字符串，用程序?qū)崿F(xiàn)
關(guān)鍵理解：
正則匹配，動態(tài)規(guī)劃思想，一個個向后追溯，后面的依賴前面的匹配成功。 正則和待匹配的字符串長度不一，統(tǒng)一到正則字符串的index索引上，每次的字符串index移動，都以匹配到的正則的index為準(zhǔn)。 正則由于*?的存在，所以有多種狀態(tài)，中間狀態(tài)儲存都需要記錄下來。然后以這些狀態(tài)為動態(tài)的中轉(zhuǎn)，繼續(xù)判斷到最后。 最后正則匹配字符串是否成功的判斷依據(jù)，就是正則字符串的最大index，是否出現(xiàn)在遍歷到最后的狀態(tài)列表中。
錯誤之處：
多處動態(tài)變化，導(dǎo)致無法入手，*沒有處理思路，沒有找到匹配成功的條件
應(yīng)用：
正則屬于多條路徑問題，可以推理到 多種渠道的問題，匹配成功當(dāng)前的才往后推 *相當(dāng)于無限向后匹配，所以無限循環(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)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/42165.html
摘要：難度題目給出一個字符串和一個要求我們給出這個字符串是否匹配這個其中通配符跟我們平常見到的一樣是和代表任意單個字符代表一個或多個字符這個題跟簡單正則匹配比較類似可以跟這里面第二個解法一樣采取類似的動態(tài)規(guī)劃解法在里取中間某個確定的字符串序列將字 Implement wildcard pattern matching with support for ? and *. ? Matches ...
摘要：當(dāng)我們遇到一個時，因為之后可能要退回至該位置重新匹配，我們要將它的下標(biāo)記錄下來，比如。但是，當(dāng)我們連續(xù)遇到兩次的情況，如何保證我還是能繼續(xù)匹配，而不是每次都退回導(dǎo)致循環(huán)呢所以我們還要記錄一個，用來記錄用上一個連續(xù)匹配到的中的下標(biāo)。 Wildcard Matching Implement wildcard pattern matching with support for ? and ...
摘要：遞歸和動規(guī)的方法沒有研究，說一下較為直觀的貪心算法。用和兩個指針分別標(biāo)記和進(jìn)行比較的位置，當(dāng)遍歷完后，若也遍歷完，說明完全配對。當(dāng)之前出現(xiàn)過，且此時和完全無法配對的時候，就一起退回在和配對過的位置。再將和逐個加繼續(xù)比較，并將后移。 Problem Implement wildcard pattern matching with support for ? and *. ? Matche...
摘要：題目鏈接這道題還是可以用的方法，用的數(shù)組來解，空間復(fù)雜度較高。和不同，這道題的符號和前面的沒有關(guān)系，不需要一起考慮。最壞的情況下，間隔出現(xiàn)且每個都要匹配很多字符，設(shè)一個平均匹配里面?zhèn)€字符，。其中，是的長度，是的長度。 Wildcard Matching 題目鏈接：https://leetcode.com/problems...這道題還是可以用Regular Expression Mat...
摘要：各一個指針，表示上一次真正到的位置。在的時候，上，增加下一步知道出界，發(fā)現(xiàn)是錯誤的所以需要回到上次的地方，即一旦走出去，無法返回，需要一個指針記錄最后的地方。 public class Solution { public boolean isMatch(String s, String p) { int idxs = 0, idxp = 0, idxmatch ...
閱讀 4063·2021-11-16 11:44
閱讀 5320·2021-10-09 09:54
閱讀 2073·2019-08-30 15:44
閱讀 1751·2019-08-29 17:22
閱讀 2826·2019-08-29 14:11
閱讀 3453·2019-08-26 13:25
閱讀 2384·2019-08-26 11:55
閱讀 1677·2019-08-26 10:37
