Hard
题目描述
一个由小写英文字母组成的原字符串，可以通过以下步骤编码：
- 任意将其分割成若干个非空子字符串的序列。
- 任意选择序列中的一些元素（可能没有），并将每个元素替换为其长度（作为数字字符串）。
- 将序列连接起来作为编码字符串。
例如，编码原字符串 “abcdefghijklmnop” 的一种方式可能是：
- 分割成序列：[“ab”, “cdefghijklmn”, “o”, “p”]。
- 选择第二和第三个元素分别替换为它们的长度。序列变为 [“ab”, “12”, “1”, “p”]。
- 连接序列的元素得到编码字符串：“ab121p”。
给定两个编码字符串 s1 和 s2，由小写英文字母和数字 1-9（包含）组成，如果存在一个原字符串可以同时编码为 s1 和 s2，则返回 true。否则，返回 false。
注意：测试用例保证 s1 和 s2 中连续数字的个数不超过 3。
示例 1：
输入：s1 = "internationalization", s2 = "i18n"
输出：true
解释：可能的原字符串是 "internationalization"。
示例 2：
输入：s1 = "l123e", s2 = "44"
输出：true
解释：可能的原字符串是 "leetcode"。
示例 3：
输入：s1 = "a5b", s2 = "c5b"
输出：false
解释：不可能存在这样的原字符串。
约束条件：
- 1 <= s1.length, s2.length <= 40
- s1 和 s2 仅由数字 1-9（包含）和小写英文字母组成
- s1 和 s2 中连续数字的个数不超过 3
解题思路
这是一道复杂的动态规划问题。核心思想是：两个编码字符串能表示同一个原字符串，当且仅当它们在每个位置上都能匹配。
解题思路：
状态设计：使用三维DP状态
(i, j, diff)，其中：i表示 s1 的当前位置j表示 s2 的当前位置diff表示两字符串在原字符串中的位置差（s1的位置 - s2的位置）
数字处理：当遇到数字时，需要考虑所有可能的分割方式。例如 “123” 可以分割为：
- 1 + 23 = 1个字符 + 23个字符
- 12 + 3 = 12个字符 + 3个字符
- 123 = 123个字符
匹配策略：
- 字母vs字母：必须相同
- 字母vs数字：调整位置差
- 数字vs数字：尝试所有可能的分割组合
优化：使用记忆化搜索避免重复计算，同时限制
diff的范围在合理区间内。
关键在于正确处理数字字符串的所有可能解释，并维护两个字符串在原字符串中的相对位置关系。
代码实现
class Solution {
public:
unordered_map<string, bool> memo;
bool possiblyEquals(string s1, string s2) {
return dfs(s1, s2, 0, 0, 0);
}
bool dfs(const string& s1, const string& s2, int i, int j, int diff) {
string key = to_string(i) + "," + to_string(j) + "," + to_string(diff);
if (memo.count(key)) return memo[key];
if (i == s1.length() && j == s2.length()) {
return memo[key] = (diff == 0);
}
if (i < s1.length() && isdigit(s1[i])) {
string num = "";
for (int k = i; k < s1.length() && isdigit(s1[k]) && k < i + 3; k++) {
num += s1[k];
int val = stoi(num);
if (dfs(s1, s2, k + 1, j, diff - val)) {
return memo[key] = true;
}
}
} else if (j < s2.length() && isdigit(s2[j])) {
string num = "";
for (int k = j; k < s2.length() && isdigit(s2[k]) && k < j + 3; k++) {
num += s2[k];
int val = stoi(num);
if (dfs(s1, s2, i, k + 1, diff + val)) {
return memo[key] = true;
}
}
} else {
if (diff > 0) {
if (j < s2.length() && dfs(s1, s2, i, j + 1, diff - 1)) {
return memo[key] = true;
}
} else if (diff < 0) {
if (i < s1.length() && dfs(s1, s2, i + 1, j, diff + 1)) {
return memo[key] = true;
}
} else {
if (i < s1.length() && j < s2.length() && s1[i] == s2[j]) {
if (dfs(s1, s2, i + 1, j + 1, 0)) {
return memo[key] = true;
}
}
}
}
return memo[key] = false;
}
};
class Solution:
def possiblyEquals(self, s1: str, s2: str) -> bool:
from functools import lru_cache
@lru_cache(None)
def dfs(i, j, diff):
if i == len(s1) and j == len(s2):
return diff == 0
if i < len(s1) and s1[i].isdigit():
num = ""
for k in range(i, min(i + 3, len(s1))):
if s1[k].isdigit():
num += s1[k]
val = int(num)
if dfs(k + 1, j, diff - val):
return True
else:
break
elif j < len(s2) and s2[j].isdigit():
num = ""
for k in range(j, min(j + 3, len(s2))):
if s2[k].isdigit():
num += s2[k]
val = int(num)
if dfs(i, k + 1, diff + val):
return True
else:
break
else:
if diff > 0:
if j < len(s2) and dfs(i, j + 1, diff - 1):
return True
elif diff < 0:
if i < len(s1) and dfs(i + 1, j, diff + 1):
return True
else:
if i < len(s1) and j < len(s2) and s1[i] == s2[j]:
if dfs(i + 1, j + 1, 0):
return True
return False
return dfs(0, 0, 0)
public class Solution {
private Dictionary<string, bool> memo = new Dictionary<string, bool>();
public bool PossiblyEquals(string s1, string s2) {
return Dfs(s1, s2, 0, 0, 0);
}
private bool Dfs(string s1, string s2, int i, int j, int diff) {
string key = $"{i},{j},{diff}";
if (memo.ContainsKey(key)) return memo[key];
if (i == s1.Length && j == s2.Length) {
return memo[key] = (diff == 0);
}
if (i < s1.Length && char.IsDigit(s1[i])) {
string num = "";
for (int k = i; k < s1.Length && char.IsDigit(s1[k]) && k < i + 3; k++) {
num += s1[k];
int val = int.Parse(num);
if (Dfs(s1, s2, k + 1, j, diff - val)) {
return memo[key] = true;
}
}
} else if (j < s2.Length && char.IsDigit(s2[j])) {
string num = "";
for (int k = j; k < s2.Length && char.IsDigit(s2[k]) && k < j + 3; k++) {
num += s2[k];
int val = int.Parse(num);
if (Dfs(s1, s2, i, k + 1, diff + val)) {
return memo[key] = true;
}
}
} else {
if (diff > 0) {
if (j < s2.Length && Dfs(s1, s2, i, j + 1, diff - 1)) {
return memo[key] = true;
}
} else if (diff < 0) {
if (i < s1.Length && Dfs(s1, s2, i + 1, j, diff + 1)) {
return memo[key] = true;
}
} else {
if (i < s1.Length && j < s2.Length && s1[i] == s2[j]) {
if (Dfs(s1, s2, i + 1, j + 1, 0)) {
return memo[key] = true;
}
}
}
}
return memo[key] = false;
}
}
var possiblyEquals = function(s1, s2) {
const memo = new Map();
function getPossibleLengths(s, start) {
const lengths = new Set();
let num = 0;
for (let i = start; i < s.length && i < start + 3 && /\d/.test(s[i]); i++) {
num = num * 10 + parseInt(s[i]);
lengths.add(num);
}
return lengths;
}
function dfs(i1, i2, diff) {
if (i1 === s1.length && i2 === s2.length) {
return diff === 0;
}
const key = `${i1},${i2},${diff}`;
if (memo.has(key)) {
return memo.get(key);
}
let result = false;
if (diff > 0) {
// s1 is ahead, need to consume from s2
if (i2 < s2.length) {
if (/[a-z]/.test(s2[i2])) {
result = dfs(i1, i2 + 1, diff - 1);
} else {
const lengths = getPossibleLengths(s2, i2);
for (const len of lengths) {
let j = i2;
while (j < s2.length && /\d/.test(s2[j])) j++;
if (dfs(i1, j, diff - len)) {
result = true;
break;
}
}
}
}
} else if (diff < 0) {
// s2 is ahead, need to consume from s1
if (i1 < s1.length) {
if (/[a-z]/.test(s1[i1])) {
result = dfs(i1 + 1, i2, diff + 1);
} else {
const lengths = getPossibleLengths(s1, i1);
for (const len of lengths) {
let j = i1;
while (j < s1.length && /\d/.test(s1[j])) j++;
if (dfs(j, i2, diff + len)) {
result = true;
break;
}
}
}
}
} else {
// diff === 0, both strings are at same position
if (i1 < s1.length && i2 < s2.length) {
const c1 = s1[i1];
const c2 = s2[i2];
if (/[a-z]/.test(c1) && /[a-z]/.test(c2)) {
if (c1 === c2) {
result = dfs(i1 + 1, i2 + 1, 0);
}
} else if (/[a-z]/.test(c1) && /\d/.test(c2)) {
const lengths = getPossibleLengths(s2, i2);
for (const len of lengths) {
let j = i2;
while (j < s2.length && /\d/.test(s2[j])) j++;
if (dfs(i1, j, -len)) {
result = true;
break;
}
}
} else if (/\d/.test(c1) && /[a-z]/.test(c2)) {
const lengths = getPossibleLengths(s1, i1);
for (const len of lengths) {
let j = i1;
while (j < s1.length && /\d/.test(s1[j])) j++;
if (dfs(j, i2, len)) {
result = true;
break;
}
}
} else {
// both are digits
const lengths1 = getPossibleLengths(s1, i1);
const lengths2 = getPossibleLengths(s2, i2);
for (const len1 of lengths1) {
let j1 = i1;
while (j1 < s1.length && /\d/.test(s1[j1])) j1++;
for (const len2 of lengths2) {
let j2 = i2;
while (j2 < s2.length && /\d/.test(s2[j2])) j2++;
if (dfs(j1, j2, len1 - len2)) {
result = true;
break;
}
}
if (result) break;
}
}
} else if (i1 === s1.length && i2 < s2.length && /\d/.test(s2[i2])) {
const lengths = getPossibleLengths(s2, i2);
for (const len of lengths) {
let j = i2;
while (j < s2.length && /\d/.test(s2[j])) j++;
if (dfs(i1, j, -len)) {
result = true;
break;
}
}
} else if (i2 === s2.length && i1 < s1.length && /\d/.test(s1[i1])) {
const lengths = getPossibleLengths(s1, i1);
for (const len of lengths) {
let j = i1;
while (j < s1.length && /\d/.test(s1[j])) j++;
if (dfs(j, i2, len)) {
result = true;
break;
}
}
}
}
memo.set(key, result);
return result;
}
return dfs(0, 0, 0);
};
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(n × m × d) |
| 空间复杂度 | O(n × m × d) |
其中 n 和 m 分别是 s1 和 s2 的长度，d 是可能的位置差范围（通常为常数）。由于连续数字不超过3位，实际的状态空间相对有限。