面试金典--面试题 16.18. 模式匹配 （正则）

题目描述

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

示例 1：
输入： pattern = “abba”, value = “dogcatcatdog”
输出： true

示例 2：
输入： pattern = “abba”, value = “dogcatcatfish”
输出： false

示例 3：
输入： pattern = “aaaa”, value = “dogcatcatdog”
输出： false

思路分析

这题说实话就适合正则，刚看了官解，一塌糊涂，还是正则吧。

先造正则表达式分组。

因为pattern 里只有a和b嘛，所以让a='\1' b='\2。

rega, regb = ('\\1', '\\2') if pattern[0] == 'a' else ('\\2', '\\1')
1

然后开始遍历pattern，替换其中字符，构造正则表达式。
遇到的第一个a和b变成捕获组'(\\w*) 用于后续引用。
剩下的a和b全部变成对应的a='\1' b='\2,意味着引用前面的ab捕获组。

然后直接用match匹配就行了。别忘了加上起始和结尾符。

看一下匹配的情况：
假设：value = “dogcatcatdog”

m = re.match(p, value)
print(m.groups())
输出:('dog', 'cat')
1
2
3

这里分情况讨论就行了，如果m为空，则说明匹配失败。

若m.groups()输出的捕获组只有一个，则是符合要求的情况。
若捕获组里两个值相等，则False。
其余情况均返回True。

完整代码

class Solution:
    def patternMatching(self, pattern: str, value: str) -> bool:
        import re
        # a为\1 b为\2
        rega, regb = ('\\1', '\\2') if pattern[0] == 'a' else ('\\2', '\\1')

        p = pattern.replace('a', '(\\w*)', 1).replace('b', '(\\w*)', 1).replace('a', rega).replace('b', regb)

        p = '^' + p + '$'
        m = re.match(p, value)
        
        if not m:
            return False
        if len(m.groups()) == 1:
            return True
        if m.groups()[0]==m.groups()[1]:
            return False
        return True

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20