> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/stringff0c_zi_fu_chuan_lei/g_decode_string.md).

# (G) Decode String

## [Decode String](https://leetcode.com/problems/decode-string/)

匆忙写的，有点丑。。之后要优化下。

步骤上不麻烦，遇到嵌套的括号，就把原始 String 变成更小的子问题，递归处理就好了。于是这题操作上总共就三件事：

* 一边扫一边记录当前数字，times 初始化 = 0；
* 找到当前括号的匹配括号；
* 括号之间就是一个新的子问题，递归处理之后把结果用循环添加就好了。

  ```java
  public String decodeString(String s) {
      if(s == null || s.length() == 0) return "";
      StringBuilder sb = new StringBuilder();

      for(int i = 0; i < s.length(); i++){
          char chr = s.charAt(i);
          if(Character.isDigit(chr)){
              int times = 0;
              while(i < s.length() && s.charAt(i) != '['){
                  times = times * 10 + (s.charAt(i) - '0');
                  i ++;
              }
              int matchIndex = findMatchIndex(s, i);
              String repeat = decodeString(s.substring(i + 1, matchIndex));

              for(int time = 0; time < times; time++){
                  sb.append(repeat);
              }
              i = matchIndex;
          } else {
              sb.append(chr);
          }
      }
      return sb.toString();
  }

  private int findMatchIndex(String s, int index){
      int count = 0;
      for(; index < s.length(); index++){
          if(s.charAt(index) == '[') count ++;
          else if(s.charAt(index) == ']') count --;

          if(count == 0) break;
      }

      return index;
  }
  ```