通配符匹配

通配符匹配

 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
 1process.stdin.resume();
 2process.stdin.setEncoding('utf-8');
 3let input = '';
 4
 5process.stdin.on('data', (data) => {
 6    input += data;
 7});
 8
 9process.stdin.on('end', () => {
10    let inputArray = input.trim().split('\n');
11    let s = inputArray[0];
12    let p = inputArray[1];
13
14    function isMatch(s, p) {
15        const m = s.length;
16        const n = p.length;
17
18        // 创建一个二维数组来保存匹配结果
19        const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
20
21        // 空字符串和空模式是匹配的
22        dp[0][0] = true;
23
24        // 处理模式字符串以 * 开头的情况
25        for (let j = 1; j <= n; j++) {
26            if (p[j - 1] === '*') {
27                dp[0][j] = dp[0][j - 1];
28            }
29        }
30
31        // 填充 DP 表格
32        for (let i = 1; i <= m; i++) {
33            for (let j = 1; j <= n; j++) {
34                if (p[j - 1] === '*') {
35                    // * 可以匹配零个或多个字符
36                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
37                } else if (p[j - 1] === '?' || p[j - 1] === s[i - 1]) {
38                    // ? 可以匹配任意单个字符，或者当前字符匹配
39                    dp[i][j] = dp[i - 1][j - 1];
40                } else {
41                    // 当前字符不匹配，并且不是通配符
42                    dp[i][j] = false;
43                }
44            }
45        }
46
47        return dp[m][n];
48    }
49
50    console.log(isMatch(s, p) ? 'TRUE' : 'FALSE');
51    process.exit();
52});

Copyright ©2010-2022 比特日记 All Rights Reserved.

Powered By 可尔物语

浙ICP备11005866号-12