模式匹配
难度:
标签:
题目描述
You are given two strings, pattern and value. The pattern string consists of just the letters a and b, describing a pattern within a string. For example, the string catcatgocatgo matches the pattern aabab (where cat is a and go is b). It also matches patterns like a, ab, and b. Write a method to determine if value matches pattern. a and b cannot be the same string.
Example 1:
Input: pattern = "abba", value = "dogcatcatdog" Output: true
Example 2:
Input: pattern = "abba", value = "dogcatcatfish" Output: false
Example 3:
Input: pattern = "aaaa", value = "dogcatcatdog" Output: false
Example 4:
Input: pattern = "abba", value = "dogdogdogdog" Output: true Explanation: "a"="dogdog",b=""，vice versa.
Note:
0 <= len(pattern) <= 10000 <= len(value) <= 1000patternonly contains"a"and"b",valueonly contains lowercase letters.
代码结果
运行时间: 29 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 计算 pattern 中 'a' 和 'b' 的数量。
* 2. 使用 Java Stream 尝试不同的字符串长度来表示 'a' 和 'b'。
* 3. 对于每个可能的长度，构建字符串并与 value 进行匹配。
* 4. 如果找到匹配的模式，返回 true；否则返回 false。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean patternMatching(String pattern, String value) {
if (pattern.isEmpty()) return value.isEmpty();
long countA = pattern.chars().filter(ch -> ch == 'a').count();
long countB = pattern.length() - countA;
if (value.isEmpty()) return countA == 0 || countB == 0;
return IntStream.range(0, value.length() / Math.toIntExact(countA) + 1)
.anyMatch(lenA -> {
int rest = value.length() - lenA * Math.toIntExact(countA);
if (countB == 0 || rest % countB == 0) {
int lenB = (countB == 0) ? 0 : rest / Math.toIntExact(countB);
int pos = 0;
String a = "", b = "";
for (char c : pattern.toCharArray()) {
if (c == 'a') {
String sub = value.substring(pos, pos + lenA);
if (a.isEmpty()) a = sub;
else if (!a.equals(sub)) return false;
pos += lenA;
} else {
String sub = value.substring(pos, pos + lenB);
if (b.isEmpty()) b = sub;
else if (!b.equals(sub)) return false;
pos += lenB;
}
}
return !a.equals(b);
}
return false;
});
}
}
解释
方法:
此题解采用模拟和试探的方法来决定两种模式 'a' 和 'b' 可能对应的字符串长度，通过穷举所有可能的长度组合。首先计算 pattern 中 'a' 和 'b' 的出现次数。如果 value 为空字符串，只有在 pattern 也不含 'a' 或 'b' 时才返回真。特殊情况处理，若 'a' 或 'b' 出现次数为1，那么总可以将 value 分配给那个模式字符。接下来，尝试每一个可能的 'a' 的长度 (len_a)，计算相应的 'b' 的长度。通过字典 d 存储 'a' 和 'b' 对应的字符串和长度。遍历 pattern，检查对应段的字符串是否匹配，如果遇到不匹配的情况则结束当前循环。如果整个 pattern 遍历完成也没有中断，说明找到了一种匹配方式。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
在处理模式匹配时，如何决定枚举'a'和'b'的长度范围？为什么选择最大长度为value的长度？
▷🦆
如果'a'和'b'在pattern中的数量完全不同，算法是如何处理这种不平衡？是否会影响长度的计算和最终匹配结果？
▷🦆
为何在确定'a'或'b'的字符串时，算法采用了断言'a'和'b'不指向相同的字符串？这种假设是否有可能限制某些边界情况下的正确匹配？
▷