Skip to content

Latest commit

 

History

History
222 lines (169 loc) · 6.82 KB

decode-string.md

File metadata and controls

222 lines (169 loc) · 6.82 KB

394. Decode String - 字符串解码

Tags - 题目标签

Description - 题目描述

EN:

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

 

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

 

Constraints:

  • 1 <= s.length <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

ZH-CN:

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

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

 

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300] 

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language Runtime Memory Submission Time
python3 36 ms 14.9 MB 2023/04/09 18:41 
class Solution:
  def decodeString(self, s: str) -> str:
    stack = []
    for c in s:
        if c != ']':
            stack.append(c)
        else:
            # Pop characters from the stack until the opening bracket is found
            temp_str = ""
            while stack and stack[-1] != '[':
                temp_str = stack.pop() + temp_str
            stack.pop()  # Remove the opening bracket

            # Find the number before the opening bracket and remove it from the stack
            k = ""
            while stack and stack[-1].isdigit():
                k = stack.pop() + k
            k = int(k)

            # Push the decoded substring back into the stack
            stack.append(temp_str * k)

    return "".join(stack)

My Notes - 我的笔记

思路：用栈。 这是刚开始写的思路：栈中只存放左右括号，需要递归以及添加一堆条件判断。

function decodeString(s: string): string {
  const parse = (start: number, end: number) => {
    let str = '';
    let counter = 0;
    const stack: string[] = [];
    let i = start;
    let leftIdx = -1;
    while (i <= end) {
      if (isNaN(Number(s[i]))) {
        if (s[i] !== '[' && s[i] !== ']') {
          if (stack.length === 0) {
            str += s[i];
          }
        } else {
          if (s[i] === '[') {
            if (stack.length === 0) {
              leftIdx = i;
            }
            stack.push(s[i]);
          } else {
            stack.pop();
            if (stack.length === 0) {
              const subStr = parse(leftIdx + 1, i - 1);
              for (let c = 0; c < counter; c++) {
                str += subStr;
              }
              leftIdx = -1;
            }
          }
        }
      } else {
        const numStart = i;
        while (!isNaN(Number(s[i]))) {
          i++;
        }
        if (stack.length === 0) {
          counter = parseInt(s.slice(numStart, i));
        }
        continue;
      }
      i++;
    }
    return str;
  }

  return parse(0, s.length - 1);
};

后来和同学交流后，发现其实可以把除了非右括号的所有东西都压入栈，更简单，而且不用递归：

class Solution:
  def decodeString(self, s: str) -> str:
    stack = []
    for c in s:
        if c != ']':
            stack.append(c)
        else:
            # Pop characters from the stack until the opening bracket is found
            temp_str = ""
            while stack and stack[-1] != '[':
                temp_str = stack.pop() + temp_str
            stack.pop()  # Remove the opening bracket

            # Find the number before the opening bracket and remove it from the stack
            k = ""
            while stack and stack[-1].isdigit():
                k = stack.pop() + k
            k = int(k)

            # Push the decoded substring back into the stack
            stack.append(temp_str * k)

    return "".join(stack)