友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

394. 字符串解码

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

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

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

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k,例如不会出现像 3a2[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]

思路分析

主要就是一个栈操作。不过,还需要注意一些细节。

使用递归处理时,最重要的是递归一次,要把括号层数减少一层,否则只能原地踏步。

  • 一刷

  • 二刷

  • 三刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Runtime: 1 ms, faster than 64.03% of Java online submissions for Decode String.
 * Memory Usage: 37.4 MB, less than 5.68% of Java online submissions for Decode String.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-28 22:08
 */
public String decodeString(String s) {
    if (Objects.isNull(s) || s.length() == 0) {
        return "";
    }
    Deque<Integer> nums = new LinkedList<>();
    Deque<String> strings = new LinkedList<>();
    int num = 0;
    StringBuilder result = new StringBuilder();
    for (char c : s.toCharArray()) {
        if (c == '[') {
            nums.addLast(num);
            strings.addLast(result.toString());
            num = 0;
            result = new StringBuilder();
        } else if (c == ']') {
            StringBuilder sb = new StringBuilder();
            Integer n = nums.removeLast();
            for (int i = 0; i < n; i++) {
                sb.append(result);
            }
            result = new StringBuilder(strings.removeLast() + sb.toString());
        } else if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        } else if (Character.isLetter(c)) {
            result.append(c);
        }
    }
    return result.toString();
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-18 16:05:13
 */
int idx = 0;
public String decodeString(String s) {
  StringBuilder sb = new StringBuilder();
  while (idx < s.length()) {
    char c = s.charAt(idx);
    if ('0' <= c && c <= '9') {
      sb.append(dfs(s));
    } else {
      sb.append(c);
      idx++;
    }
  }
  return sb.toString();
}

private String dfs(String s) {
  int cnt = 0;
  boolean isEnd = false;
  StringBuilder sb = new StringBuilder();
  while (idx < s.length()) {
    char c = s.charAt(idx);
    if ('0' <= c && c <= '9') {
      if (isEnd) {
        sb.append(dfs(s));
        continue;
      }
      int num = c - '0';
      if (cnt == 0) {
        cnt = num;
      } else {
        cnt = 10 * cnt + num;
      }
      idx++;
    } else if ('a' <= c && c <= 'z') {
      sb.append(c);
      idx++;
    } else if (c == '[') {
      isEnd = true;
      idx++;
    } else if (s.charAt(idx) == ']') {
      idx++;
      break;
    }
  }
  StringBuilder result = new StringBuilder();
  for (int j = 0; j < cnt; j++) {
    result.append(sb);
  }
  return result.toString();
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-10-14 19:36:59
 */
public String decodeString(String s) {
  StringBuilder sb = new StringBuilder();
  int index = 0;
  while (index < s.length()) {
    char c = s.charAt(index);
    if ('a' <= c && c <= 'z') {
      sb.append(c);
      index++;
    } else {
      int start = index;
      int left = 0, right = -1;
      while (index < s.length() && right < left) {
        char c1 = s.charAt(index);
        if (c1 == '[') {
          left++;
        } else if (c1 == ']') {
          if (right == -1) {
            right = 1;
          } else {
            right++;
          }
        }
        index++;
      }
      String part = s.substring(start, index - 1);
      int i1 = part.indexOf("[");
      int repeat = Integer.parseInt(part.substring(0, i1));
      String is = decodeString(part.substring(i1 + 1));
      sb.append(is.repeat(repeat));
    }
  }
  return sb.toString();
}