javascript - 解码字符串 - Javascript
问题描述
我正在尝试在 javascript 中实现解码字符串算法。
问题:给定一个编码字符串,返回它的解码字符串。
编码规则是:k[encoded_string],其中方括号内的encoded_string 正好重复k 次。请注意,k 保证为正整数。
您可以假设输入字符串始终有效;没有多余的空格,方括号格式正确等。
此外,您可以假设原始数据不包含任何数字,并且数字仅用于那些重复数字 k。例如,不会有像 3a 或 2[4] 这样的输入。
示例 1:
输入:s = "3[a]2[bc]" 输出:"aaabcbc"
示例 2:
输入:s = "3[a2[c]]" 输出:"accacccacc"
示例 3:
输入:s = "2[abc]3[cd]ef" 输出:"abcabccdcdcdef"
示例 4:
输入:s = "abc3[cd]xyz" 输出:"abccdcdcdxyz"
我的尝试:
var decodeString = function(s) {
if(!s || s.length === 0) return "";
let map = {
'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6,
'7': 7, '8': 8, '9': 9
};
let res = "";
const dfs = (str) => {
//let res = "";
const arr = str.split("");
for(let i=0; i<arr.length; i++) {
if(arr[i] === '[') {
// call dfs
const close = getClosePos(i, arr);
dfs(arr.splice(i+1,close-(i+1)).join(""));
} else if(map[arr[i]] !== undefined) {
// repet N next letters
let k = map[arr[i]];
while(k > 0) {
res += dfs(arr.splice(i+1,arr.length).join(""));
k--;
}
} else if(arr[i] !== ']') {
res += arr[i];
}
}
//return res;
}
dfs(s);
return res;
};
const getClosePos = (i, arr) => {
for(let j=i; j<arr.length; j++) {
if(arr[j] === ']')
return j;
}
return 0;
}
我的输出是:"undefinedundefinedundefined"
谢谢
解决方案
您可以用正则表达式替换字符串并获得所需的嵌套替换,直到没有更多的字符串可供替换。
const decodeString = string => {
let repeat
do {
repeat = false;
string = string.replace(/(\d+)\[([^\[\]]+)\]/g, (_, c, v) => {
repeat = true;
return v.repeat(c);
});
} while (repeat);
return string;
}
console.log(decodeString("3[a]2[bc]")); // "aaabcbc"
console.log(decodeString("3[a2[c]]")); // "accaccacc"
console.log(decodeString("2[abc]3[cd]ef")); // "abcabccdcdcdef"
console.log(decodeString("abc3[cd]xyz")); // "abccdcdcdxyz"
如果您希望简化/更新/探索表达式,它已在regex101.com的右上角面板中进行了说明。如果您有兴趣,可以在此调试器链接中观看匹配步骤或修改它们。调试器演示了 RegEx 引擎如何逐步使用一些示例输入字符串并执行匹配过程。
正则表达式电路
jex.im可视化正则表达式:
推荐阅读
- class - Kotlin 继承/子类
- git - 手动比较功能分支的主要类并仅进行这些更改,或者我应该将主要开发分支合并到此功能中
- html - Blazor HTML 渲染问题
- python - 网页抓取指定表
- c++ - 将 -lcrypto 与未定义的引用链接的 Mingw32 错误
- reactjs - React 保持旧状态 - 新状态未更新
- kubernetes - 如果未指定主机,如何访问 k8s 入口
- ruby-on-rails - Rails路由重定向使用约束和块?
- scala - Scala Spark,比较两个 DataFrames 并选择另一列的值
- mysql - 将字符串 (csv) 传递给存储过程,搜索列 (csv) 包含