class Solution {
public:
bool patternMatching(string pattern, string value) {
}
};
面试题 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=""，反之也符合规则
提示：
1 <= len(pattern) <= 10000 <= len(value) <= 1000pattern只包含字母"a"和"b"，value仅包含小写字母。原站题解
javascript 解法, 执行用时: 568 ms, 内存消耗: 47.1 MB, 提交时间: 2023-04-22 11:20:52
/**
* @param {string} pattern
* @param {string} value
* @return {boolean}
*/
var patternMatching = (pattern, value) => {
const map = new Map() // 保存a和b所对应的单词
const set = new Set() // 用于确保map中的a和b不会对应相同的单词
const match = (pattern, value, map, set) => { // pattern子串和value子串是否匹配
if (pattern == '') // 递归的出口 如果pattern为空字符串，但value不是
return value == '' // 则不匹配，否则，匹配
const pChar = pattern[0] // 获取pattern的首字符
if (map.has(pChar)) { // map中，如果pChar已经有对应的单词
if (!value.startsWith(map.get(pChar))) // 如果value不是以该单词开头 返回false
return false // 否则继续考察剩余的pattern和value
return match(pattern.substring(1), value.substring(map.get(pChar).length), map, set)
}
for (let i = -1; i < value.length; i++) { // pChar可以是''，所以从-1开始
const word = value.substring(0, i + 1) // 从value串的开头截取不同长度的单词
if (set.has(word)) continue // 别的pChar已经对应了该单词 跳过该单词
map.set(pChar, word) // 当前pChar和对应的单词存入map
set.add(word) // 单词存入set集合
if (match(pattern.substring(1), value.substring(i + 1), map, set)) {
return true // match递归调用，考察剩余pattern和剩余的value串是否匹配
} // 如果match的结果是true，直接返回true，否则进行下面的回溯
map.delete(pChar) // map中删除pChar和它对应的单词
set.delete(word) // set中删除该单词，继续考察下一个单词
}
return false // 遍历了所有情况，都没有返回true，只有返回false
}
return match(pattern, value, map, set) // 入口，整个pattern和整个value串是否匹配
};
javascript 解法, 执行用时: 84 ms, 内存消耗: 41.2 MB, 提交时间: 2023-04-22 11:20:18
/**
* @param {string} pattern
* @param {string} value
* @return {boolean}
*/
var patternMatching = function(pattern, value) {
if (pattern === "") {
return value === "";
}
let group = 1;
let a = '';
let b = '';
let reg = '';
for (const char of pattern.split('')) {
if (char === 'a') {
if (a) {
reg += a;
}
else {
reg += '(\\w*)';
a = '\\' + group++;
}
}
else if (char === 'b') {
if (b) {
reg += b;
}
else {
reg += '(\\w*)';
b = '\\' + group++;
}
}
}
const match = new RegExp('^' + reg + '$').exec(value);
return Boolean(match) && match[1] !== match[2];
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.9 MB, 提交时间: 2023-04-22 11:19:05
class Solution {
public boolean patternMatching(String pattern, String value) {
int count_a = 0, count_b = 0;
for (char ch: pattern.toCharArray()) {
if (ch == 'a') {
++count_a;
} else {
++count_b;
}
}
if (count_a < count_b) {
int temp = count_a;
count_a = count_b;
count_b = temp;
char[] array = pattern.toCharArray();
for (int i = 0; i < array.length; i++) {
array[i] = array[i] == 'a' ? 'b' : 'a';
}
pattern = new String(array);
}
if (value.length() == 0) {
return count_b == 0;
}
if (pattern.length() == 0) {
return false;
}
for (int len_a = 0; count_a * len_a <= value.length(); ++len_a) {
int rest = value.length() - count_a * len_a;
if ((count_b == 0 && rest == 0) || (count_b != 0 && rest % count_b == 0)) {
int len_b = (count_b == 0 ? 0 : rest / count_b);
int pos = 0;
boolean correct = true;
String value_a = "", value_b = "";
for (char ch: pattern.toCharArray()) {
if (ch == 'a') {
String sub = value.substring(pos, pos + len_a);
if (value_a.length() == 0) {
value_a = sub;
} else if (!value_a.equals(sub)) {
correct = false;
break;
}
pos += len_a;
} else {
String sub = value.substring(pos, pos + len_b);
if (value_b.length() == 0) {
value_b = sub;
} else if (!value_b.equals(sub)) {
correct = false;
break;
}
pos += len_b;
}
}
if (correct && !value_a.equals(value_b)) {
return true;
}
}
}
return false;
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2023-04-22 11:18:51
func patternMatching(pattern string, value string) bool {
countA, countB := 0, 0
for i := 0; i < len(pattern); i++ {
if pattern[i] == 'a' {
countA++
} else {
countB++
}
}
if countA < countB {
countA, countB = countB, countA
tmp := ""
for i := 0; i < len(pattern); i++ {
if pattern[i] == 'a' {
tmp += "b"
} else {
tmp += "a"
}
}
pattern = tmp
}
if len(value) == 0 {
return countB == 0
}
if len(pattern) == 0 {
return false
}
for lenA := 0; countA * lenA <= len(value); lenA++ {
rest := len(value) - countA * lenA
if (countB == 0 && rest == 0) || (countB != 0 && rest % countB == 0) {
var lenB int
if countB == 0 {
lenB = 0
} else {
lenB = rest / countB
}
pos, correct := 0, true
var valueA, valueB string
for i := 0; i < len(pattern); i++ {
if pattern[i] == 'a' {
sub := value[pos:pos+lenA]
if len(valueA) == 0 {
valueA = sub
} else if valueA != sub {
correct = false
break
}
pos += lenA
} else {
sub := value[pos:pos+lenB]
if len(valueB) == 0 {
valueB = sub
} else if valueB != sub {
correct = false
break
}
pos += lenB
}
}
if correct && valueA != valueB {
return true
}
}
}
return false
}
python3 解法, 执行用时: 28 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-22 11:18:38
class Solution:
def patternMatching(self, pattern: str, value: str) -> bool:
count_a = sum(1 for ch in pattern if ch == 'a')
count_b = len(pattern) - count_a
if count_a < count_b:
count_a, count_b = count_b, count_a
pattern = ''.join('a' if ch == 'b' else 'b' for ch in pattern)
if not value:
return count_b == 0
if not pattern:
return False
for len_a in range(len(value) // count_a + 1):
rest = len(value) - count_a * len_a
if (count_b == 0 and rest == 0) or (count_b != 0 and rest % count_b == 0):
len_b = 0 if count_b == 0 else rest // count_b
pos, correct = 0, True
value_a, value_b = None, None
for ch in pattern:
if ch == 'a':
sub = value[pos:pos+len_a]
if not value_a:
value_a = sub
elif value_a != sub:
correct = False
break
pos += len_a
else:
sub = value[pos:pos+len_b]
if not value_b:
value_b = sub
elif value_b != sub:
correct = False
break
pos += len_b
if correct and value_a != value_b:
return True
return False