《程序员面试金典（第 6 版）》16.18. 模式匹配

[Tcdian]

《程序员面试金典（第 6 版）》16.18. 模式匹配

你有两个字符串，即pattern和value。 pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

Example 1

输入： pattern = "abba", value = "dogcatcatdog"
输出： true

Example 2

输入： pattern = "abba", value = "dogcatcatfish"
输出： false

Example 3

输入： pattern = "aaaa", value = "dogcatcatdog"
输出： false

Example 4

输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则

Note

• 0 <= len(pattern) <= 1000
• 0 <= len(value) <= 1000
• 你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。

[Tcdian]

Solution

• TypeScript Solution

function patternMatching(pattern: string, value: string): boolean {
    if (pattern === '') {
        return value === '';
    }
    let p = '^';
    let aPattern = '';
    let bPattern = '';
    for (let i = 0; i < pattern.length; i++) {
        if (pattern[i] === 'a') {
            if (aPattern === '') {
                p += '([a-z]*)';
                aPattern = bPattern === '' ? '\\1' : '\\2';
            } else {
                p += aPattern;
            }
        } else if (pattern[i] === 'b') {
            if (bPattern === '') {
                p += '([a-z]*)';
                bPattern = aPattern === '' ? '\\1' : '\\2'; 
            } else {
                p += bPattern;
            }
        }
    }
    p += '$';
    let result = false;
    const match = value.match(new RegExp(p));
    if (match) {
        const [, aGroup, bGroup] = match;
        result = aGroup !== bGroup;
    }
    return result;
};