題目
簡要貼下題目与涡，具體詳見這里：
給定一個(gè)字符串 (s) 和一個(gè)字符模式 (p)。實(shí)現(xiàn)支持 '.' 和 '*' 的正則表達(dá)式匹配。
'.' 匹配任意單個(gè)字符。
'*' 匹配零個(gè)或多個(gè)前面的元素解取。
匹配應(yīng)該覆蓋整個(gè)字符串 (s) ，而不是部分字符串返顺。
說明:
s 可能為空禀苦，且只包含從 a-z 的小寫字母。
p 可能為空遂鹊，且只包含從 a-z 的小寫字母振乏，以及字符 . 和 *。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個(gè)字符串秉扑。
解題過程
初始想法
首先我在沒有背景知識的情況下慧邮，素人想法，從字符串 s 第一個(gè)字符開始與正則中第一個(gè) pattern 匹配邻储，如果符合赋咽，則看第二個(gè)字符是否符合第一個(gè) pattern旧噪，如果不符合則看下是否符合第二個(gè) pattern吨娜。這樣相當(dāng)于有兩個(gè)游標(biāo)在字符串和正則上向后游動，不斷匹配淘钟，當(dāng)無法匹配上的時(shí)候就是不 match宦赠。
回溯
當(dāng)然這是一個(gè)很基礎(chǔ)的概念。因?yàn)轭}目中涉及 * 這個(gè)可以多次匹配的通配符（其實(shí)題目已經(jīng)很簡化了）米母，所以可能出現(xiàn)同一個(gè)字符字串匹配到多種 pattern 組合的情況勾扭。這就不單單是兩個(gè)游標(biāo)依次往下走的問題了。所以我決定先查下正則匹配的通用規(guī)則铁瞒。
像上面提到的這個(gè)問題就涉及到回溯問題了妙色，舉個(gè)簡單的例子：
字符串：abbbc
正則：/ab{1,3}bbc/
匹配的過程是：
第6步由于c沒法和b{1,3}后面的b匹配上，所以我們把與b{1,3}匹配上的bbb吐出一位（也就是回退一位）拿這個(gè)b去匹配正則b{1,3}后面的b慧耍。這種由于往前走嘗試一種路徑（或者匹配規(guī)則）走不通身辨，需要嘗試另一種路徑的方式叫做回溯。在稍微復(fù)雜的正則中可能一次匹配的過程中會涉及非常多次的回溯芍碧。稍微詳盡的例子看這里 煌珊。
代碼
按照初步掌握的知識先嘗試寫寫看（會結(jié)合注釋和偽代碼）：
// 主函數(shù)
function isMatch( s, p ) {
}
我想了下由于在匹配的過程中需要把整個(gè)正則拆分成小的子 pattern，那么我先把 p 分解了泌豆，省的游標(biāo)一邊向后走定庵，一邊還要判斷解析正則。思路是把[a-z], ., [a-z], . 分別摘出來。
// 主函數(shù)
function isMatch( s, p ) {
let patterns = toPatterns( p );
// 開始匹配
}
function toPatterns( p ) {
let result = [];
if ( p.length===0 ) {
return result;
}
for( let i = 0; i < p.length; ) {
let currentP = p[ i ];
let nextP = p[ i+1 ];
if ( nextP!=='*' ) {
// 單個(gè)字母
if (
currentP !== '.' &&
currentP !== '*'
) {
result.push( {
type: 'char',
keyword: currentP
} );
i++;
continue;
}
// 單個(gè).
if ( currentP==='.' ) {
result.push( {
type: '.'
} );
i++
continue;
}
// 單個(gè)*
if ( currentP==='*' ) {
throw 'invalid pattern';
}
} else {
if ( currentP==='.' ) {
result.push( {
type: '.*'
} );
i += 2;
continue;
} else {
result.push( {
type: 'char*',
keyword: currentP
} );
i += 2;
continue;
}
}
}
return result;
}
然后開始循環(huán)判斷：
// 主函數(shù)
function isMatch( s, p ) {
let patterns = toPatterns( p );
// 開始匹配
/*
先判斷邊際條件
s 為空 p 為空
s 為空
p 為空
的情況蔬浙，具體代碼就省略了
*/
let subPattern = patterns.shift();
let strIndex = 0;
// 當(dāng) patterns 和 s 都輪詢完了才算完結(jié)
while(
subPattern ||
strIndex < s.length;
) {
// 用字符和正則的子模式進(jìn)行比較
if (
subPattern &&
subPattern.type==='char'
s[strIndex]===subPattern.keyword
) {
// 如果是 [a-z] 的正則猪落，且匹配上了，那么字符串和正則都需要往下走一步：
subPattern = patterns.shift();
strIndex++
} else if (
// 如果是 . 的正則匹配上了
) {
// 字符串和正則都需要往下走一步：
subPattern = patterns.shift();
strIndex++
} else if (
// 如果是 [a-z]* 的正則匹配上了
) {
// 字符串下走一步畴博，正則還可以用
strIndex++
} else if (
// 如果是 .* 的正則匹配上了
) {
// 字符串下走一步许布，正則還可以用
strIndex++
} else {
// 如果沒有匹配上，這里就開始考慮Ｒ锘巍Ｃ弁佟！回溯ＪＴ唷！
}
}
}
function toPatterns( p ) {
// 省略
}
代碼寫到這里咱揍，我發(fā)現(xiàn)了個(gè)問題颖榜，如果要回溯，我要用非常多的變量記錄各種情況煤裙，寫很多分支條件掩完，沒法寫啊。參考了別人的代碼硼砰，發(fā)現(xiàn)把循環(huán)該成遞歸且蓬，能很好的解決這個(gè)問題（針對這道題目只有[a-z], .的情況會產(chǎn)生回溯）：
var isMatch = function(s, p) {
return isMatchImpl( s, toPatterns(p) );
};
function toPatterns( p ) {
// 省略
}
function isMatchImpl( s, patterns ) {
// 開始匹配
/*
先判斷邊際條件
s 為空 patterns 為空
s 為空
patterns 為空
的情況，具體代碼就省略了
*/
let p = patterns[ 0 ];
if (
p.type==='char' &&
s[ 0 ]===p.keyword
) {
return isMatchImpl( s.substr(1), patterns.slice(1) );
} else if (
p.type==='.' &&
s[ 0 ]
) {
return isMatchImpl( s.substr(1), patterns.slice(1) );
} else if (
p.type==='char*'
) {
if ( s[ 0 ]===p.keyword ) {
// 這里通過邏輯或和遞歸题翰，把回溯的各個(gè)條件依次執(zhí)行
return isMatchImpl( s, patterns.slice(1) ) || isMatchImpl( s.substr(1), patterns ) || isMatchImpl( s.substr(1), patterns.slice(1) );
} else {
// 這里通過邏輯或和遞歸恶阴，把回溯的各個(gè)條件依次執(zhí)行
return isMatchImpl( s, patterns.slice(1) )
}
} else if (
p.type==='.*'
) {
if ( s ) {
// 這里通過邏輯或和遞歸，把回溯的各個(gè)條件依次執(zhí)行
return isMatchImpl( s, patterns.slice(1) ) || isMatchImpl( s.substr(1), patterns ) || isMatchImpl(s.substr(1), patterns.slice(1));
} else {
// 這里通過邏輯或和遞歸豹障，把回溯的各個(gè)條件依次執(zhí)行
return isMatchImpl( s, patterns.slice(1) );
}
} else {
return false;
}
}
看下代碼里面的注釋冯事，通過邏輯或的邏輯短路原則，結(jié)合遞歸血公，就把回溯的各個(gè)路徑寫成一行了昵仅。循環(huán)和遞歸真是好基友，各有各的適用場景累魔。代碼的功能完成了摔笤，通過了官方的測試用例。
動態(tài)規(guī)劃
代碼完成了薛夜，但是執(zhí)行效率很有問題籍茧。看下上面講回溯例子時(shí)候的圖片梯澜，當(dāng)回溯的時(shí)候如果 subpattern 沒有變寞冯，且 strindex 沒有變渴析，那么結(jié)果是一致的，也就是說如果多次執(zhí)行可以被記錄下來吮龄，不用每次都判斷 subPattern 和 s[strIndex] 是否匹配俭茧。這個(gè)思路和優(yōu)化斐波那契數(shù)列是否有點(diǎn)相似，就是對計(jì)算過的結(jié)果用空間換時(shí)間漓帚，對于相同的計(jì)算條件只需要計(jì)算一次母债。這個(gè)思路再加上這道題目，背后的原理其實(shí)就是動態(tài)規(guī)劃的概念尝抖。
我簡單說下什么叫動態(tài)規(guī)劃：
- 將待求解的問題分解為若干個(gè)子問題毡们。
- 按順序求解子階段，前一子問題的解昧辽，為后一子問題的求解提供了有用的信息衙熔。
- 在求解任一子問題時(shí)，列出各種可能的局部解搅荞，通過決策保留那些有可能達(dá)到最優(yōu)的局部解红氯，丟棄其他局部解。
這個(gè)好像和我們正則匹配的過程不謀而合了：
- 匹配的過程是必須每個(gè) subpattern 都匹配成功咕痛。
- 下一個(gè) subpattern 所要匹配的字符取決于上一個(gè) subpattern 用到哪個(gè)字符痢甘。
- 當(dāng)一條匹配路徑走不通，通過回溯尋找另一條可能的匹配路徑茉贡。
而動態(tài)規(guī)劃在算法中的應(yīng)用塞栅，其一大優(yōu)化策略就是充分利用前面保存的子問題的解來減少重復(fù)計(jì)算。所以改造下代碼：
const P_TYPE_CHAR = 1;
const P_TYPE_ANY_CHAR = 2;
const P_TYPE_CHAR_ANY_TIME = 3;
const P_TYPE_ANY_CHAR_ANY_TIME = 4;
const Q_DOT = '.';
const Q_STAR = '*';
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
return isMatchImpl( s, 0, toPatterns(p), 0 );
};
function toPatterns( p ) {
// 省略
}
let Cache = {};
function isMatchImpl( s, sIndex, patterns, pIndex ) {
if ( sIndex===s.length && pIndex===patterns.length ) {
return true;
}
if ( sIndex < s.length && pIndex===patterns.length ) {
return false;
}
let cacheKey = `${sIndex}-${pIndex}`;
if ( Cache[cacheKey]!==undefined ) {
return Cache[cacheKey];
}
let p = patterns[ pIndex ];
if (
p.type===P_TYPE_CHAR &&
s[ sIndex ]===p.keyword
) {
Cache[ cacheKey ] = true;
return isMatchImpl( s, ++sIndex, patterns, ++pIndex );
} else if (
p.type===P_TYPE_ANY_CHAR &&
s[ sIndex ]
) {
Cache[ cacheKey ] = true;
return isMatchImpl( s, ++sIndex, patterns, ++pIndex );
} else if (
p.type===P_TYPE_CHAR_ANY_TIME
) {
Cache[ cacheKey ] = true;
if ( s[ sIndex ]===p.keyword ) {
return isMatchImpl( s, sIndex, patterns, ++pIndex ) || isMatchImpl( s, ++sIndex, patterns, pIndex ) || isMatchImpl( s, ++sIndex, patterns, ++pIndex );
} else {
Cache[ cacheKey ] = false;
return isMatchImpl( s, sIndex, patterns, ++pIndex )
}
} else if (
p.type===P_TYPE_ANY_CHAR_ANY_TIME
) {
Cache[ cacheKey ] = true;
if ( s ) {
return isMatchImpl( s, sIndex, patterns, ++pIndex ) || isMatchImpl( s, ++sIndex, patterns, pIndex ) || isMatchImpl(s, ++sIndex, patterns, ++pIndex );
} else {
return isMatchImpl( s, sIndex, patterns, ++pIndex );
}
} else {
Cache[ cacheKey ] = false;
return false;
}
}
