【Day 4 】2024-12-04 - 394. 字符串解码

[azl397985856]

394. 字符串解码

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/decode-string/

前置知识

• 栈
• 括号匹配

  题目描述

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

编码规则为: 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"

[shangjiaw]

 代码

def decodeString(s):
    res = []

    for i in s:
        if i != ']':
            res.append(i)
        else:
            subString = ''
            while res[-1] != '[':
                subString = res.pop() + subString
            res.pop()

            k = ''
            while res and res[-1].isdigit():
                k = res.pop() + k

            res.append( subString * int(k) )    

    return ''.join(res)

print(decodeString("3[a]2[bc]"))
#"aaabcbc"

print(decodeString("3[a2[c]]"))
#"accaccacc"

print(decodeString("2[abc]3[cd]ef"))
#"abcabccdcdcdef"

print(decodeString("abc3[cd]xyz"))
#"abccdcdcdxyz"

复杂度分析 - 时间复杂度：O(N) - 空间复杂度：O(N)

[tongxw]

class Solution {
    public String decodeString(String s) {
        Deque<String> strStack = new LinkedList<>();
        Deque<Integer> numStack = new LinkedList<>();

        int number = 0;
        StringBuilder ans = new StringBuilder();

        // number can be more than 1 digit
        // two stacks for the decoded string and number
        for (char c : s.toCharArray()) {
             if (Character.isDigit(c)) {
                number = number * 10 + (c - '0');

             } else if (Character.isLetter(c)) {
                ans.append(c);
             } else if (c == '[') {
                // push the number and sub string to the stack
                numStack.push(number);
                number = 0;

                strStack.push(ans.toString());
                ans.setLength(0);
             } else {
                // repeat the string
                int repeat = numStack.pop();
                String cur = ans.toString();
                ans.setLength(0);
                while (repeat-- > 0) {
                    ans.append(cur);
                }

                // append the repeated string to the top string of the stack
                String top = strStack.pop();
                String appendString = top + ans.toString();

                // decode complete
                ans = new StringBuilder(appendString);

             }
        }

        return ans.toString();
    }
}

[CHXBilly]

class Solution(object): def decodeString(self, s): """ :type s: str :rtype: str """ number_stack = [] string_stack = [] current_string = "" current_number = 0

    for char in s:
        if char.isdigit():
            current_number = current_number * 10 + int(char) #need to include *10 for s= "123[leetcode]", for anything bigger than 9
        elif char == '[':
            number_stack.append(current_number)
            string_stack.append(current_string)
            current_number = 0
            current_string = ""
        elif char == ']':
            #when reach the right ), look at whats in side the () and the repeat number related to it
            repeat_number = number_stack.pop() #the list delete the last one
            previous_string = string_stack.pop() 
            current_string = previous_string + current_string * repeat_number
        else:
            current_string += char

    return current_string

[XiaogaoDDD]

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        stack <int> nums;
        stack <string> strs;
        int num = 0;
        int len = s.size();
        for(int i = 0; i < len; ++ i)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                num = num * 10 + s[i] - '0';
            }
            else if((s[i] >= 'a' && s[i] <= 'z') ||(s[i] >= 'A' && s[i] <= 'Z'))
            {
                res = res + s[i];
            }
            else if(s[i] == '[') 
            {
                nums.push(num);
                num = 0;
                strs.push(res); 
                res = "";
            }
            else
            {
                int times = nums.top();
                nums.pop();
                for(int j = 0; j < times; ++ j)
                    strs.top() += res;
                res = strs.top(); 
                strs.pop();
            }
        }
        return res;
    }
};

[tuuna]

include

include

class Solution { public: string decodeString(string s) { std::stack counts; std::stack strings; std::string currentString; int count = 0;

    for (char ch : s) {
        if (isdigit(ch)) {
            count = count * 10 + ch - '0';
        } else if (ch == '[') {
            counts.push(count);
            strings.push(currentString);
            count = 0;
            currentString.clear();
        } else if (ch == ']') {
            std::string decodedString = strings.top();
            strings.pop();
            int repeatCount = counts.top();
            counts.pop();
            for (int i = 0; i < repeatCount; i++) {
                decodedString += currentString;
            }
            currentString = decodedString;
        } else {
            currentString += ch;
        }
    }

    return currentString;
}

};