调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业
提示

你有两个字符串,即patternvaluepattern字符串由字母"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="",反之也符合规则

提示:

  • 1 <= len(pattern) <= 1000
  • 0 <= len(value) <= 1000
  • 你可以假设pattern只包含字母"a""b"value仅包含小写字母。
通过次数
19.7K
提交次数
58.2K
通过率
33.9%


相关企业

提示 1
从蛮力解法开始。你能试一下a和b的所有可能性吗?

提示 2
观察其中一个子字符串,a或b都可以,必须从字符串的开头开始。这减少了可能性的种类。

提示 3
不要忘记处理pattern中的第一个字符是b的可能性。

提示 4
谨慎地选择分析时间复杂度的方式。如果遍历O(n2)个子字符串,每个子字符串都进行O(n)次的字符串比较,那么总体运行时间为O(n3)。

提示 5
假设你确定了一个模式中“a”部分的值。b有多少种可能性?

提示 6
由于a的值决定b的值(反之亦然),并且a或b必须出现于值的起始处,所以你应该只有O(n)种可能来分解模式串。

提示 7
你应该能够有一个O(n2)的算法。

评论 (0)

《程序员面试金典(第 6 版)》独家授权
本书是原谷歌资深面试官的经验之作,帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的,帮助你轻松应战 IT 名企技术面试。
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
pattern =
"abba"
value =
"dogcatcatdog"
Source