常用通配符* 匹配另一个字符串（不含通配符或者不解析通配符）
字符串 a="abcd" 是否和另外一个包含通配符的字符串b="ab*d" 是否相等
将两个字符串散列成矩阵的形式
| a | b | c | d | |
|---|---|---|---|---|
| a | ||||
| b | ||||
| * | ||||
| d |
每一个矩阵中的值代表的是截至到该位置的时候字符串的部分是否匹配
所以如果想知道两个字符串是否匹配的时候，只需知道d-d的时候是否匹配即可
| a | b | c | d | |
|---|---|---|---|---|
| a | T | F | F | F |
| b | F | T | F | F |
| * | F | T | T | F |
| d | F | F | F | T |
这只是我们手工计算的值，我们分析这个矩阵 x代表行， y 代表列
当 （2，2）的时候 x = b, y= b 所以 x=y 只代表的是当前位置相等， 若想知道截至到当前位置字符串是否相等，我们需要知道左上的值UL（1，1）是否相等 ，并与当前位置做
与运算，所以（2，2）为真 ，这是x，y不是通配符*的情况(x,y) = x== y && UL（3，2）时x值为
*,UL值为F 按照上面的显然不成立， 但是*是通配符可以通配一个，多个，或者空字符串， 所以U（2，2）为真的时候（3，2）为真（此时*匹配空）或 L(3,1)为真的时候（2，3）也可为真（此时*匹配一个或者多个）所以当x时*时（x,y） = U || L上面的结果建立在第一行和第一列值已经存在的情况如何计算第一行，以及第一列的值，我们将行和列之前分别填一空字符串
| '' | a | b | c | d | |
|---|---|---|---|---|---|
| '' | |||||
| a | T | F | F | F | |
| b | F | T | F | F | |
| * | F | T | T | F | |
| d | F | F | F | T |
此时计算第一行， 第一列的值
| '' | a | b | c | d | |
|---|---|---|---|---|---|
| '' | T | F | F | F | F |
| a | F | T | F | F | F |
| b | F | F | T | F | F |
| * | F | F | T | T | F |
| d | F | F | F | F | T |
依然符合上面的情况
O（1,1）x='',y='' 字符串其实位置所以为T, (1，2) 时 '' != a && L(1,1)为假所以为F， 第一行第一列计算相似（注意*号的时候）所以结果如上图
- 当第一行以及第一列计算出来的时候， 根据1，2 可以计算出最尾部的值
js代码
/**
* string a 正常字符串
* string b 带通配符的字符串
*/
function sim(a, b){
a = a.split('')
a.unshift('')
b = b.split('')
b.unshift('')
let c = [];
for (let i =0; i<b.length; i++) {
c[i] = []
c[i][0] = (b[i] === a[0] || b[i] === '*') && (i-1 < 0 ? true: c[i-1][0])
}
for(let i =0; i<a.length; i++){
c[0][i] = (a[i] === b[0] || a[i] === '*') && (i-1 < 0 ? true: c[0][i-1])
}
for(let i =1; i < b.length; i++){
for(let j =1; j < a.length; j++){
cl = c[i][j-1]
cu = c[i-1][j]
clu = c[i-1][j-1]
if(b[i] === '*'){
c[i][j] = cl || cu
}else{
c[i][j] = a[j] === b[i] && clu
}
}
}
return c[b.length-1][a.length-1]
}
go 代码
/**
* 判断一个字符串是否和另一个包含通配符的字符串相等
* a 普通字符串
* b 带通配符字符串
*/
func sim(a string, b string) bool {
wildcard := "*" // 通配符
as := append([]string{""}, strings.Split(a, "")...) // 打断成数组并在前面追加""
bs := append([]string{""}, strings.Split(b, "")...) // 打断成数组并在前面追加""
c := make([][]bool, len(bs)) // 矩形图
cl := false // 当前位置的左坐标
cu := false // 当前位置的上坐标
clu := false // 当前位置的左上坐标
// 初始化第一列的值
last := false //上行，上列值
for i := range bs {
// 初始化矩阵的每一行
c[i] = make([]bool, len(as))
// 上一列的值
if i-1 < 0 {
last = true
} else {
last = c[i-1][0]
}
c[i][0] = (bs[i] == as[0] || wildcard == bs[i]) && last
}
// 初始化第一行的值
for i := range as {
if i-1 < 0 {
last = true
} else {
last = c[0][i-1]
}
c[0][i] = (as[i] == bs[0] || as[i] == wildcard) && last
}
// 列行循环初始化所有矩阵值
for i := 1; i < len(bs); i++ {
for j := 1; j < len(as); j++ {
cl = c[i][j-1]
cu = c[i-1][j]
clu = c[i-1][j-1]
if bs[i] == wildcard {
c[i][j] = cl || cu
} else {
c[i][j] = (as[j] == bs[i]) && clu
}
}
}
return c[len(bs)-1][len(as)-1]
}
