LeetCode 程序员面试金典面试题 16.18 模式匹配

2020-06-22 2020-06-22 约 1542 字预计阅读 4 分钟

本题是一道优秀的面试题，题目难度不大，仅仅需要小学的知识即可解出核心难题，但是却需要细致的思考才能写出逻辑清晰、没有错误的代码。

题目描述

题目大意

本题极其类似字符串的正则匹配，当然是极端简化版。模式串 pattern 的格式固定而且最多只有两种字符 a 和 b，每种字符对应 value 的一个子串。求 pattern 中 a 和 b 替换为相应子串之后是不是和 value 完全相等。

注意：a 和 b 的内容不可相同

输入与输出

示例输入为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
Input 1:
pattern = "abba"
value = "dogcatcatdog"

Input 2:
pattern = "abba"
value = "dogcatcatfish"

Input 3:
pattern = "aaaa"
value = "dogcatcatdog"

Input 4:
pattern = "abba"
value = "dogdogdogdog"

对应输出为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Output 1:
true

Output 2:
false

Output 3:
false

Output 4:
true

第 4 例输入中，可以令 “a”=“dogdog” 且 b=""，反之也符合规则

注意：

pattern 和 value 的长度可以为 0
pattern 中只有 a 或 b
value 只包含小写字母

解题思路

简要概括本题的解法简单直白，就是暴力枚举。

本题实际难度不大，关键在于两点：

正确处理边界条件
理清思路，写出清晰的自然语言流程或伪代码

注意：为了便于理解和阅读，下文所示的解法只保证理论时间复杂度满足要求，但未进行细节优化。

处理边界条件

pattern 和 value 的长度都可能为 0，需要仔细地分情况处理：

长度都为 0：答案为 true
只有 pattern 长度为 0：答案为 false
只有 value 长度为 0：pattern 只有一种字符时为 true，反之为 false

收缩输入范围

处理完边界条件之后，只有 pattern 和 value 长度都不为 0 的情况，但是字符 ‘a’ 和 ‘b’ 实际上仍然是平等的（或者说是对称的），即 pattern 中 ‘a’ 和 ‘b’ 互换后不会影响答案。这样，不妨规定 pattern 的起始字符必须为 ‘a’，如果为 ‘b’ 则互换 pattern 中的 ‘a’ 和 ‘b’。这样处理之后就能把输入格式固定，方便后序处理，省略冗余的相似代码。

理清枚举流程

枚举算法的核心是找出所有 a 和 b 的可能内容，然后根据 pattern 拼接为新的字符串，比较是否和 value 相等。但是，枚举两个变量确实比较麻烦，何况它们之间又有比较复杂的关系，直接枚举会引入太多条件判断。但是，仔细思考就能发现其实只需要枚举 a 的值即可。

首先，一旦 a 的长度确定，其内容必然确定。因为在上面“收缩输入范围”的操作之后，pattern 起始字符必定为 ‘a’，即 a 一定是 value 的开头，可以使用 substring 操作轻松获取 a 的值。

其次，一旦 a 的长度确定则 b 的长度也必然可以确定。因为 a 和 b 的数量和长度关系如下：

$$ \begin{cases} len_{pattern} = cnt_a + cnt_b \
len_{value} = len_a \times cnt_a + len_b \times cnt_b \end{cases} $$

这其中 pattern 和 value 的长度，以及 a 和 b 的个数都是确定的，那么根据 a 的长度求 b 的长度也就非常简单。

最后，一旦 b 的长度确定，那么它的内容也必然确定。我们可以根据 pattern 中开头有多少个 ‘a’ 在 ‘b’ 之前，确定在 value 的开头有多少个 a，然后丢弃这些 a 再向后就能马上发现 b 的内容。

注意：a 和 b 的长度都是整数不一定在所有枚举的情况中都有合法解。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    fun patternMatching(pattern: String, value: String): Boolean {
        if (pattern.isEmpty() && value.isEmpty()) return true
        if (pattern.isEmpty()) return false
        if (pattern[0] == 'b') return patternMatching(normalize(pattern), value)
        val noB = pattern.all { it == 'a' }
        if (value.isEmpty()) return noB

        if (noB) {
            if (value.length % pattern.length != 0) return false
            val a = value.substring(0, value.length / pattern.length)
            return a.repeat(pattern.length) == value
        }

        val cmpStr = StringBuilder()
        for (endOfA in 0..value.length) {
            cmpStr.clear()
            val a = value.substring(0, endOfA)
            val b = getB(pattern, value, a) ?: continue
            if (a == b) continue
            pattern.forEach { cmpStr.append(if (it == 'a') a else b) }
            if (cmpStr.toString() == value) return true
        }
        return false
    }

    private fun normalize(pattern: String): String {
        if (pattern[0] == 'a') return pattern
        val re = StringBuilder()
        pattern.forEach {
            re.append(if (it == 'a') 'b' else 'a')
        }
        return re.toString()
    }

    private fun getB(pattern: String, value: String, a: String): String? {
        val cntOfA = pattern.count { it == 'a' }
        val cntOfB = pattern.length - cntOfA
        val lenA = a.length
        val remain = value.length - lenA * cntOfA
        if (remain < 0 || remain % cntOfB != 0) return null

        val lenB = remain / cntOfB
        var tmp = 0
        while (pattern[tmp] == 'a') {
            tmp++
        }
        tmp *= lenA
        return value.substring(tmp, lenB + tmp)
    }
}

获取 b 的内容和组合 cmpStr 都需要遍历 pattern，而 cmpStr 和 value 比较需要遍历 value，所以总的时间复杂度为 $O((len_{pattern} + len_{value}) \times len_{value})$，即 $O(len^2_{value})$

代码额外说明如下：

本段代码对 pattern 只有 ‘a’ 的情况进行了剪枝处理，而且不影响程序的可读性
不引入 StringBuilder 而直接使用下标可能可以提高效率，但是会极大地损害易读性，得不偿失

目录

LeetCode 程序员面试金典 面试题 16.18 模式匹配