第394题---Decode String

• 题意描述

  • 给定一个字符串，这个字符串只包含数字，字母和[]中括号，数字代表后面紧跟的中括号内字母重复的次数，可以嵌套，把这个字符串进行解码成正常的字符串

• 思路

  • 因为有嵌套，所以需要栈保存上面的状态信息，又如果使用栈，又可以使用递归解决
  • 递归，首先判断是不是数字，如果不是数字，直接把字母加入临时的字符串中，如果是数字，记录数字，递归中括号内的字符，重复数字次数

• 代码

  class Solution {
  public:
      string decodeString(string s, int& i) {
          string res;
          
          while(i < s.length() && s[i] != ']') {
              if(!isdigit(s[i])) 
                  res += s[i++];
              else {
                  int n = 0;
                  while(i < s.length() && isdigit(s[i]))
                      n = n * 10 + s[i++] - '0';
                      
                  i ++;
                  string t = decodeString(s, i);
                  i ++;
                  
                  while(n-- > 0)
                      res += t;
              }
          }
          return res;
      }
  
      string decodeString(string s) {
          int i = 0;
          return decodeString(s, i);
      }
  };