常用通配符* 匹配另一個(gè)字符串（不含通配符或者不解析通配符）
字符串 a="abcd" 是否和另外一個(gè)包含通配符的字符串b="ab*d" 是否相等
將兩個(gè)字符串散列成矩陣的形式
| a | b | c | d | |
|---|---|---|---|---|
| a | ||||
| b | ||||
| * | ||||
| d |
每一個(gè)矩陣中的值代表的是截至到該位置的時(shí)候字符串的部分是否匹配
所以如果想知道兩個(gè)字符串是否匹配的時(shí)候，只需知道d-d的時(shí)候是否匹配即可
| a | b | c | d | |
|---|---|---|---|---|
| a | T | F | F | F |
| b | F | T | F | F |
| * | F | T | T | F |
| d | F | F | F | T |
這只是我們手工計(jì)算的值，我們分析這個(gè)矩陣 x代表行， y 代表列
當(dāng) （2，2）的時(shí)候 x = b, y= b 所以 x=y 只代表的是當(dāng)前位置相等， 若想知道截至到當(dāng)前位置字符串是否相等，我們需要知道左上的值UL（1，1）是否相等 ，并與當(dāng)前位置做
與運(yùn)算，所以（2，2）為真 ，這是x，y不是通配符*的情況(x,y) = x== y && UL（3，2）時(shí)x值為
*,UL值為F 按照上面的顯然不成立， 但是*是通配符可以通配一個(gè)，多個(gè)，或者空字符串， 所以U（2，2）為真的時(shí)候（3，2）為真（此時(shí)*匹配空）或 L(3,1)為真的時(shí)候（2，3）也可為真（此時(shí)*匹配一個(gè)或者多個(gè)）所以當(dāng)x時(shí)*時(shí)（x,y） = U || L上面的結(jié)果建立在第一行和第一列值已經(jīng)存在的情況如何計(jì)算第一行，以及第一列的值，我們將行和列之前分別填一空字符串
| '' | a | b | c | d | |
|---|---|---|---|---|---|
| '' | |||||
| a | T | F | F | F | |
| b | F | T | F | F | |
| * | F | T | T | F | |
| d | F | F | F | T |
此時(shí)計(jì)算第一行， 第一列的值
| '' | 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='' 字符串其實(shí)位置所以為T, (1，2) 時(shí) '' != a && L(1,1)為假所以為F， 第一行第一列計(jì)算相似（注意*號的時(shí)候）所以結(jié)果如上圖
- 當(dāng)?shù)谝恍幸约暗谝涣杏?jì)算出來的時(shí)候， 根據(jù)1，2 可以計(jì)算出最尾部的值
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 代碼
/**
* 判斷一個(gè)字符串是否和另一個(gè)包含通配符的字符串相等
* a 普通字符串
* b 帶通配符字符串
*/
func sim(a string, b string) bool {
wildcard := "*" // 通配符
as := append([]string{""}, strings.Split(a, "")...) // 打斷成數(shù)組并在前面追加""
bs := append([]string{""}, strings.Split(b, "")...) // 打斷成數(shù)組并在前面追加""
c := make([][]bool, len(bs)) // 矩形圖
cl := false // 當(dāng)前位置的左坐標(biāo)
cu := false // 當(dāng)前位置的上坐標(biāo)
clu := false // 當(dāng)前位置的左上坐標(biāo)
// 初始化第一列的值
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
}
// 列行循環(huán)初始化所有矩陣值
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]
}
