Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

字符串解码 #252

Open
louzhedong opened this issue May 4, 2021 · 0 comments
Open

字符串解码 #252

louzhedong opened this issue May 4, 2021 · 0 comments

Comments

@louzhedong
Copy link
Owner

习题

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例 1:

输入:s = "3[a]2[bc]"
输出:"aaabcbc"
示例 2:

输入:s = "3[a2[c]]"
输出:"accaccacc"
示例 3:

输入:s = "2[abc]3[cd]ef"
输出:"abcabccdcdcdef"
示例 4:

输入:s = "abc3[cd]xyz"
输出:"abccdcdcdxyz"

思路

题目中同时有数字和字母,所以我们可以使用两个栈来分别保存他们

当碰到字母,加入到当前字符串

当碰到数字,重新计算当前数字

当碰到'[',将当前数字和当前字符串分别推入栈

当碰到']',将当前字符串扩展为数字栈顶的数字的倍数

解答

javascript

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    var numStack = [],
        strStack = [],
        num = 0,
        str = "";
    for (var i = 0; i < s.length; i++) {
        var current = s[i];
        if (current == '[') {
            numStack.push(num);
            strStack.push(str);
            num = 0;
            str = "";
        } else if (current == ']') {
            str = strStack.pop() + str.repeat(numStack.pop());
        } else if (isNaN(current)) { // 字母
            str += current;
        } else {  // 数字
            num = num * 10 + Number(current);
        }
    }
    return str;
};

go

func decodeString(s string) string {
    numStack := make([]int, 0)
    strStack := make([]string, 0)
    num := 0
    str := ""
    for _, char := range s {
        if char == '[' {
            numStack = append(numStack, num)
            strStack = append(strStack, str)
            num = 0
            str = ""
        } else if char == ']' {
            if (len(strStack) > 0) {
                str = strStack[len(strStack) - 1] + strings.Repeat(str, numStack[len(numStack) - 1])
                strStack = strStack[: len(strStack) - 1]
                numStack = numStack[: len(numStack) - 1]
            } else {
                str = strings.Repeat(str, numStack[len(numStack) - 1])
                numStack = numStack[: len(numStack) - 1]
            }
        } else if (char >= '0' && char <= '9') {
            num = num * 10 + int(char - '0')
        } else {
            str += string(char)
        }
    }
    return str
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant