题解 | #字符串通配符#
字符串通配符
https://www.nowcoder.com/practice/43072d50a6eb44d2a6c816a283b02036
三种思路
1. 递归，我试了会超时，不知道什么原因
2. 正则，题目没限制，应该也可以
3. 动态规划
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let count = 1
let s1, s2
rl.on('line', function (line) {
if (count == 1) {
s1 = line.trim()
} else {
s2 = line.trim()
}
count++
});
rl.on('close', function () {
// 递归
// const dfs = (rule, target) => {
// if (rule == '' && target == '') return true
// else if (rule == '' && target !== '') return false
// else if (rule !== '' && target == '') return (rule.replace('*', '') == '')
// else {
// let match = false
// match = (rule[0] == '?' && /\w/.test(target[0])) || rule[0].toLowerCase() == target[0].toLowerCase()
// if (rule[0] == '*') {
// // 匹配 0 个 或者 匹配多个
// return dfs(rule.slice(1), target) || dfs(rule, target.slice(1))
// } else {
// return match && (dfs(rule.slice(1), target.slice(1)))
// }
// }
// }
// console.log(dfs(s1, s2)) // 正则
// s1 = s1.replace(/\?/g, '[a-z0-9]').replace(/\*/g, '.*')
// console.log(new RegExp('^' + s1 + '$', 'i').test(s2))
//动态规划
let len1 = s1.length
let len2 = s2.length
let dp = new Array(len1+1).fill(0).map(_ => new Array(len2+1).fill(false))
dp[0][0] = true
if (s1[0] == "*") {
dp[1][0] = true
}
for (let i = 1; i <= len1; i++) {
for (let j = 1; j <= len2; j++) {
if (s1[i-1] == '?' && /[a-z0-9]/i.test(s2[j-1])) {
dp[i][j] = dp[i-1][j-1]
}
else if (s1[i-1] == "*") {
dp[i][j] = dp[i-1][j] || dp[i-1][j-1] || dp[i][j-1]
}
else {
dp[i][j] = dp[i-1][j-1] && s1[i-1].toLowerCase() == s2[j-1].toLowerCase()
}
}
}
console.log(dp[len1][len2])
})
