LeetCode 题解工作台
同源字符串检测
原字符串由小写字母组成，可以按下述步骤编码： 任意将其 分割 为由若干 非空 子字符串组成的一个 序列 。 任意选择序列中的一些元素（也可能不选择），然后将这些元素替换为元素各自的长度（作为一个数字型的字符串）。 重新 顺次连接 序列，得到编码后的字符串。 例如，编码 "abcdefghijklmn…
2
题型
1
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
function possiblyEquals(s1: string, s2: string): boolean { const n = s1.length,
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
原字符串由小写字母组成，可以按下述步骤编码：
- 任意将其 分割 为由若干 非空 子字符串组成的一个 序列 。
- 任意选择序列中的一些元素（也可能不选择），然后将这些元素替换为元素各自的长度（作为一个数字型的字符串）。
- 重新 顺次连接 序列，得到编码后的字符串。
例如，编码 "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" 可以作为原字符串 - "internationalization" -> 分割： ["internationalization"] -> 不替换任何元素 -> 连接： "internationalization"，得到 s1 - "internationalization" -> 分割： ["i", "nternationalizatio", "n"] -> 替换： ["i", "18", "n"] -> 连接： "i18n"，得到 s2
示例 2：
输入：s1 = "l123e", s2 = "44" 输出：true 解释："leetcode" 可以作为原字符串 - "leetcode" -> 分割： ["l", "e", "et", "cod", "e"] -> 替换： ["l", "1", "2", "3", "e"] -> 连接： "l123e"，得到 s1 - "leetcode" -> 分割： ["leet", "code"] -> 替换： ["4", "4"] -> 连接： "44"，得到 s2
示例 3：
输入：s1 = "a5b", s2 = "c5b" 输出：false 解释：不存在这样的原字符串 - 编码为 s1 的字符串必须以字母 'a' 开头 - 编码为 s2 的字符串必须以字母 'c' 开头
示例 4：
输入：s1 = "112s", s2 = "g841" 输出：true 解释："gaaaaaaaaaaaas" 可以作为原字符串 - "gaaaaaaaaaaaas" -> 分割： ["g", "aaaaaaaaaaaa", "s"] -> 替换： ["1", "12", "s"] -> 连接： "112s"，得到 s1 - "gaaaaaaaaaaaas" -> 分割： ["g", "aaaaaaaa", "aaaa", "s"] -> 替换： ["g", "8", "4", "1"] -> 连接 "g841"，得到 s2
示例 5：
输入：s1 = "ab", s2 = "a2" 输出：false 解释：不存在这样的原字符串 - 编码为 s1 的字符串由两个字母组成 - 编码为 s2 的字符串由三个字母组成
提示：
1 <= s1.length, s2.length <= 40s1和s2仅由数字1-9和小写英文字母组成s1和s2中连续数字数不超过3
解题思路
方法一
function possiblyEquals(s1: string, s2: string): boolean {
const n = s1.length,
m = s2.length;
let dp: Array<Array<Set<number>>> = Array.from({ length: n + 1 }, v =>
Array.from({ length: m + 1 }, w => new Set()),
);
dp[0][0].add(0);
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= m; j++) {
for (let delta of dp[i][j]) {
// s1为数字
let num = 0;
if (delta <= 0) {
for (let p = i; i < Math.min(i + 3, n); p++) {
if (isDigit(s1[p])) {
num = num * 10 + Number(s1[p]);
dp[p + 1][j].add(delta + num);
} else {
break;
}
}
}
// s2为数字
num = 0;
if (delta >= 0) {
for (let q = j; q < Math.min(j + 3, m); q++) {
if (isDigit(s2[q])) {
num = num * 10 + Number(s2[q]);
dp[i][q + 1].add(delta - num);
} else {
break;
}
}
}
// 数字匹配s1为字母
if (i < n && delta < 0 && !isDigit(s1[i])) {
dp[i + 1][j].add(delta + 1);
}
// 数字匹配s2为字母
if (j < m && delta > 0 && !isDigit(s2[j])) {
dp[i][j + 1].add(delta - 1);
}
// 两个字母匹配
if (i < n && j < m && delta == 0 && s1[i] == s2[j]) {
dp[i + 1][j + 1].add(0);
}
}
}
}
return dp[n][m].has(0);
}
function isDigit(char: string): boolean {
return /^\d{1}$/g.test(char);
}
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of states, roughly O(n1 * n2 * maxCount^2), where n1 and n2 are lengths of s1 and s2 and maxCount is the maximum consecutive digit value. Space complexity is similar due to memoization storage of each unique DP state. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you considering digits in s1 and s2 as letter counts correctly?
- question_mark
Can you describe the DP state and its transitions for this problem?
- question_mark
Have you memoized overlapping subproblems to avoid recomputation?
常见陷阱
外企场景- error
Misinterpreting multi-digit numbers in s1 or s2 as separate counts instead of a single placeholder.
- error
Forgetting to track remaining letters when a digit consumes multiple positions in the original string.
- error
Assuming all letters must match directly without accounting for numeric replacements.
进阶变体
外企场景- arrow_right_alt
Check if an original string exists given multiple encoded strings, extending to more than two inputs.
- arrow_right_alt
Allow digits in encoding to represent zero letters, introducing optional skips in the original string.
- arrow_right_alt
Constrain original strings to only certain alphabets or lengths, adding additional DP restrictions.