| comments | difficulty | edit_url | rating | source | tags | ||
|---|---|---|---|---|---|---|---|
true |
困难 |
2803 |
第 265 场周赛 Q4 |
|
原字符串由小写字母组成，可以按下述步骤编码：
- 任意将其 分割 为由若干 非空 子字符串组成的一个 序列 。
- 任意选择序列中的一些元素（也可能不选择），然后将这些元素替换为元素各自的长度（作为一个数字型的字符串）。
- 重新 顺次连接 序列，得到编码后的字符串。
例如，编码 "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);
}