Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

通配符匹配

Posted on Edited on In , ,
Symbols count in article: 3k Reading time ≈ 3 mins.

来源Leetcode第44题通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*‘ 的通配符匹配。

  • ‘?’ 可以匹配任何单个字符。

  • ‘*‘ 可以匹配任意字符串（包括空字符串）。
    两个字符串完全匹配才算匹配成功。

    说明:

  • s 可能为空，且只包含从 a-z 的小写字母。

  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 2:

输入:
s = “aa”
p = “*“
输出: true
解释: ‘*‘ 可以匹配任意字符串。

和之前那题正则表达式匹配略有不同。

代码同第10题：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

class Solution {
//Method one

	//采用数组memo标记i j位置的匹配情况
    Boolean[][] memo;
    public boolean isMatch(String s, String p) {
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return isMatch(s.toCharArray(), 0, p.toCharArray(), 0);
    }
	
    //两个参数分别为匹配串和模式串
	//i j 分别对应两个字符串起始位置
    private boolean isMatch(char[] ss, int i, char[] ps, int j) {
	
		//这一句重点，如果memo备忘录有值说明这里已经匹配过了
        if(memo[i][j] != null) return memo[i][j];
        
        boolean result = false;
		//如果已经到了模式串尾，需检查匹配串
        if(j == ps.length) {
            result = (i == ss.length);
        } else {
		//第一次匹配的情况
            boolean firstMatch = i != ss.length && (ss[i] == ps[j] || ps[j] == '?');
			//如果模式串开头为'*‘
			//意味着可以跳过当前匹配串的字符或者跳过当前模式串中的字符
            if(ps[j] == '*') {
                result = (i != ss.length && isMatch(ss, i + 1, ps, j)) || isMatch(ss, i, ps, j + 1);
            } else {
			//不为'*'
			//则要检查初次是否匹配以及剩下的是否匹配
                result = firstMatch && isMatch(ss, i + 1, ps, j + 1);
            } 
        }
        //写入结果到memo备忘录里
        memo[i][j] = result;
        return result;
    }
	
//Method Two

public boolean isMatch(String text, String pattern) {
		// 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况，
		// 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了
		boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
		// dp[len][len] 代表两个空串是否匹配了，"" 和 "" ，当然是 true 了。
		dp[text.length()][pattern.length()] = true;

		// 从 len 开始减少
		for (int i = text.length(); i >= 0; i--) {
			for (int j = pattern.length(); j >= 0; j--) {
				// dp[text.length()][pattern.length()] 已经进行了初始化
				if (i == text.length() && j == pattern.length())
					continue;
				//相比之前增加了判断是否等于 * 
				boolean first_match = (i < text.length() && j < pattern.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '?' || pattern.charAt(j) == '*'));
				if (j < pattern.length() && pattern.charAt(j) == '*') {
                    //将 * 跳过 和将字符匹配一个并且 pattern 不变两种情况
					dp[i][j] = dp[i][j + 1] || first_match && dp[i + 1][j];
				} else {
					dp[i][j] = first_match && dp[i + 1][j + 1];
				}
			}
		}
		return dp[0][0];
	}

//Method Three

boolean isMatch(String str, String pattern) {
    int s = 0, p = 0, match = 0, starIdx = -1;     
    //遍历整个字符串
    while (s < str.length()){
        // 一对一匹配，两指针同时后移。
        if (p < pattern.length()  && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
            s++;
            p++;
        }
        // 碰到 *，假设它匹配空串，并且用 startIdx 记录 * 的位置，记录当前字符串的位置，p 后移
        else if (p < pattern.length() && pattern.charAt(p) == '*'){
            starIdx = p;
            match = s;
            p++;
        }
        // 当前字符不匹配，并且也没有 *，回退
        // p 回到 * 的下一个位置
        // match 更新到下一个位置
        // s 回到更新后的 match 
        // 这步代表用 * 匹配了一个字符
        else if (starIdx != -1){
            p = starIdx + 1;
            match++;
            s = match;
        }
        //字符不匹配，也没有 *，返回 false
        else return false;
    }
 
    //将末尾多余的 * 直接匹配空串 例如 text = ab, pattern = a*******
    while (p < pattern.length() && pattern.charAt(p) == '*')
        p++;

    return p == pattern.length();
}

 
}