HOT100——正規表達式比對（JS實作）

題目描述

解題思路

• 本題采用的是回溯的思想。
• 主要需要考慮的情況有以下幾種

1. 字元串和模式串的字元相等。
2. 模式串的字元為點。
3. 模式串為*的時候，分兩種情況讨論，一是0次，一是多次。

解題代碼

var isMatch = function (s, p) {
    return helper(s, p);
    function helper(str, pattern) {
        if (pattern.length === 0) {
            if (str.length === 0) {
                return true;
            } else {
                return false;
            }
        }
        // 不是 * 号的情況
        if (str.length > 2 && (str[0] === pattern[0] || pattern[0] === '.') && pattern[1] !== '*') {
            res = helper(str.slice(1),pattern.slice(1));
        } else if (str.length > 0 && (str[0] === pattern[0] || pattern[0] === '.') && pattern[1] === '*'){
            // 這是 *号 代表0次的情況        多次的情況
            res = helper(str,pattern.slice(2)) || helper(str.slice(1),pattern)
        } else {
            if (str.length > 0 && (str[0] === pattern[0] || pattern[0] === '.') && pattern[1] !== '*') {
                res = helper(str.slice(1),pattern.slice(1)); 
            } else if (pattern[1] === '*') {
                res = helper(str,pattern.slice(2))
            } else {
                return false;
            }
        }
        return res;
    }
};
複制代碼      

啟示

• 學會在多種限制條件下使用遞歸回溯解決問題。

參考連結（優先看下邊的這個）

juejin.cn/post/696319…