leetcode通配符匹配_leecode路由匹配

个人感觉比较好理解的是回溯的方法：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        lens=len(s)
        lenp=len(p)
        steps=0
        stepp=0
        p_star_idx=-1
        s_p_star_idx=-1
        while steps<lens:
            if stepp<lenp and p[stepp] in ['?',s[steps]]:
                steps+=1
                stepp+=1
            elif stepp<lenp and p[stepp]=='*':
                p_star_idx=stepp
                s_p_star_idx=steps
                stepp+=1
            elif p_star_idx==-1:
                return False
            else:
                stepp=p_star_idx+1
                steps=s_p_star_idx+1
                s_p_star_idx=steps
        while stepp<lenp and p[stepp]=='*':
            stepp+=1
        return stepp==lenp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

可能比较难理解的地方就是那个p_star_idx和s_p_star_idx的用法，这两个就是分别记录*出现的地方和可能的下一次匹配的地点。
理解了这个，这种思路也就理解了。