leetcode-面试题 16.18. 模式匹配

本文主要是介绍leetcode-面试题 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

示例 4：

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

提示：

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

解题思路

完全没思路。。。看了题解照着写的。这个题我觉得关键在于枚举，而且字符串的长度是一个突破口。。。

记$n_a$为pattern中a出现的次数，$l_a$为pattern a对应的字符串长度，则对于能够匹配的字符串，应该能够满足：
$$n_a\ast l_a+n_b\ast l_b=l_v$$
其中$l_v$是value串的长度。
$n_a$和$n_b$都是已知量，所以这是一个二元一次方程组，并且$l_a,l_b$都是大于等于0的整数，所以可以通过枚举的方式来求解。

1. 对$l_a$来说，取值范围为：$[0,\frac{l_v}{n_a}]$
2. 对$l_a$进行枚举，等式成立的条件是：$l_b=\frac{l_v-n_a\ast l_a}{n_b}$也是大于等于0的整数

枚举出$l_a,l_b$的所有可能后，再根据具体的长度，在value中找对应的子串，判断：

1. 符合pattern a的所有子串是否相同
2. 符合pattern b的所有子串是否相同
3. 符合pattern a的子串是否和符合pattern b的子串相同

即可。

枚举过程中因为出现了分数，有一些小问题需要处理：
对$l_a$枚举时，$n_a$是分母，需要考虑分母为0的情况。这里可以直接用a代替出现次数较多的pattern，即当pattern不为空时，默认$n_a\ge 1$

代码

class Solution:def patternMatching(self, pattern: str, value: str) -> bool:if not pattern:return not value# enumerate la, lb# a是pattern中出现次数较多的cnt_dict = {}for each_char in pattern:cnt_dict[each_char] = cnt_dict.get(each_char, 0) + 1na = cnt_dict.get('a', 0)nb = cnt_dict.get('b', 0)if na < nb:pattern = ''.join(['b' if item == 'a' else 'a' for item in pattern])na, nb = nb, nalv = len(value)possible_lengths = []for la in range(0, lv // na + 1):if nb:lb = (lv - na * la) / nbif lb == int(lb):possible_lengths.append((la, int(lb)))else:if lv / na == la:possible_lengths.append((la, 0))break# check if a_values are equal, b_values are equalprint(possible_lengths)while possible_lengths:cur_start = 0a_values = []b_values = []            la, lb = possible_lengths.pop()for each_p in pattern:if each_p == 'a':a_values.append(value[cur_start:cur_start + la])cur_start += laelse:b_values.append(value[cur_start:cur_start + lb])cur_start += lbprint(a_values, b_values)if len(set(a_values)) <= 1 and len(set(b_values)) <= 1 and set(a_values) != set(b_values):return Truereturn False

这篇关于leetcode-面试题 16.18. 模式匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---