如何检测两字符串模式匹配？实现对应匹配函数的解决方案

这个问题的核心是要建立双向的映射关系——既要保证模式串里的同一个字符对应输入串里固定的子串，也要保证输入串里的同一个子串只对应模式串里的唯一字符，这样才能避免出现“一对多”或者“多对一”的不匹配情况。

实现思路拆解 #

• 先处理边界情况：如果模式串为空，输入串也必须为空才匹配；只要其中一个为空另一个不为空，直接返回false。
• 用回溯+哈希表的方式来尝试分割输入串：
  • 用一个哈希表patternMap记录模式字符到输入子串的映射；
  • 用另一个哈希表strMap记录输入子串到模式字符的映射，避免重复映射；
  • 通过递归逐步匹配每个模式字符对应的子串，匹配失败就回溯，尝试其他可能的子串长度。

完整代码实现 #

function matchPattern(pattern, input) {
    // 边界情况处理
    if (!pattern && !input) return true;
    if (!pattern || !input) return false;

    const patternMap = new Map();
    const strMap = new Map();

    // 辅助递归函数：pIdx是当前处理的pattern索引，iIdx是当前处理的input索引
    function backtrack(pIdx, iIdx) {
        // 终止条件：两个串都处理完了，匹配成功
        if (pIdx === pattern.length && iIdx === input.length) return true;
        // 一个处理完另一个没处理完，匹配失败
        if (pIdx === pattern.length || iIdx === input.length) return false;

        const currentChar = pattern[pIdx];
        // 如果当前模式字符已经有映射了
        if (patternMap.has(currentChar)) {
            const expectedStr = patternMap.get(currentChar);
            // 检查input从当前位置开始是否是预期的子串
            if (input.slice(iIdx, iIdx + expectedStr.length) === expectedStr) {
                // 继续匹配下一个字符
                return backtrack(pIdx + 1, iIdx + expectedStr.length);
            } else {
                // 不符合预期，匹配失败
                return false;
            }
        } else {
            // 当前模式字符没有映射，尝试所有可能的子串长度
            // 子串最小长度是1，最大长度是input剩余长度减去pattern剩余字符数+1（每个后续字符至少占1位）
            const maxLen = input.length - iIdx - (pattern.length - pIdx - 1);
            for (let len = 1; len <= maxLen; len++) {
                const currentStr = input.slice(iIdx, iIdx + len);
                // 如果这个子串已经被其他模式字符映射了，跳过
                if (strMap.has(currentStr)) continue;

                // 建立双向映射
                patternMap.set(currentChar, currentStr);
                strMap.set(currentStr, currentChar);

                // 递归尝试下一个字符，如果成功就返回true
                if (backtrack(pIdx + 1, iIdx + len)) {
                    return true;
                }

                // 回溯：删除当前映射，尝试下一个长度
                patternMap.delete(currentChar);
                strMap.delete(currentStr);
            }
            // 所有可能的子串都尝试过了，匹配失败
            return false;
        }
    }

    return backtrack(0, 0);
}

// 测试示例
console.log(matchPattern("aabbaa", "catcatdogdogcatcat")); // 输出 true
console.log(matchPattern("abba", "dogcatcatdog")); // 输出 true
console.log(matchPattern("abba", "dogcatcatfish")); // 输出 false
console.log(matchPattern("abc", "catdogbird")); // 输出 true
console.log(matchPattern("abc", "catcatbird")); // 输出 false

关键细节说明 #

1. 双向映射的必要性：比如如果模式串是"ab"，输入串是"catcat"，如果只单向记录a→cat，会错误地允许b→cat，但双向映射会检测到cat已经被a映射，从而拒绝这个匹配，返回正确的false。
2. 子串长度的限制：计算maxLen是为了避免无效尝试——比如剩下3个模式字符，输入串只剩3个字符，那当前子串最多只能取1位，否则后续字符没有足够的长度匹配。
3. 回溯的作用：当当前子串匹配失败时，删除之前建立的映射，尝试下一个可能的子串长度，确保所有可能的分割方式都被遍历到。

内容的提问来源于stack exchange，提问作者zero_cool