LeetCode 程序员面试金典 面试题 16.18 模式匹配
本题是一道优秀的面试题,题目难度不大,仅仅需要小学的知识即可解出核心难题,但是却需要细致的思考才能写出逻辑清晰、没有错误的代码。
题目描述
原题链接如下: 面试题 16.18. 模式匹配
题目大意
本题极其类似字符串的正则匹配,当然是极端简化版。模式串 pattern 的格式固定而且最多只有两种字符 a 和 b,每种字符对应 value 的一个子串。求 pattern 中 a 和 b 替换为相应子串之后是不是和 value 完全相等。
注意:a 和 b 的内容不可相同
输入与输出
示例输入为:
|
|
对应输出为:
|
|
第 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 的长度都是整数不一定在所有枚举的情况中都有合法解。
代码
|
|
获取 b 的内容和组合 cmpStr 都需要遍历 pattern,而 cmpStr 和 value 比较需要遍历 value,所以总的时间复杂度为 $O((len_{pattern} + len_{value}) \times len_{value})$,即 $O(len^2_{value})$
代码额外说明如下:
- 本段代码对 pattern 只有 ‘a’ 的情况进行了剪枝处理,而且不影响程序的可读性
- 不引入
StringBuilder
而直接使用下标可能可以提高效率,但是会极大地损害易读性,得不偿失