leetcode：394. 字符串解码

题目

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例：

  1. 输入：s = "3[a]2[bc]"
  2. 输出："aaabcbc"
  1. 输入：s = "3[a2[c]]"
  2. 输出："accaccacc"
  1. 输入：s = "2[abc]3[cd]ef"
  2. 输出："abcabccdcdcdef"
  1. 输入：s = "abc3[cd]xyz"
  2. 输出："abccdcdcdxyz"

解答 & 代码

解法一：模拟 + 递归

  1. class Solution {
  2. private:
  3.     // 将字符串 s 重复 k 次并返回
  4.     string repeatStringKTimes(string s, int k)
  5.     {
  6.         string result = "";
  7.         for(int i = 0; i < k; ++i)
  8.             result += s;
  9.         return result;
  10.     }
  11. public:
  12.     string decodeString(string s) {
  13.         string result = "";        // 结果
  14.         int idx = 0;            // 当前下标
  15.         // 遍历字符串 s
  16.         while(idx < s.size())
  17.         {
  18.             // 1. 处理字母
  19.             while(idx < s.size() && (s[idx] >= 'a' && s[idx] <= 'z'))
  20.             {
  21.                 result += s[idx];
  22.                 ++idx;
  23.             }
  25.             // 2. 处理 k[encoded_string]，括号里面可能存在嵌套括号
  26.             // 2.1 处理数字 k
  27.             int number = 0;        // 重复次数 k
  28.             while(idx < s.size() && (s[idx] >= '0' && s[idx] <= '9'))
  29.             {
  30.                 number = number * 10 + s[idx] - '0';
  31.                 ++idx;
  32.             }            
  33.             // 2.2 跳过 "["
  34.             if(s[idx] == '[')
  35.                 ++idx;
  36.             // 2.3 处理括号中的 encoded_string
  37.             string curStr = "";        // 括号中的 encoded_string，即待被重复的字符串
  38.             while(idx < s.size() && s[idx] != ']')
  39.             {
  40.                 // 如果是字母，直接加到 curStr
  41.                 if(idx < s.size() && s[idx] >= 'a' && s[idx] <= 'z')
  42.                     curStr += s[idx];
  43.                 // 如果是数字，则提取内容 k_2[encoded_string_2]，递归处理
  44.                 else if(s[idx] >= '0' && s[idx] <= '9')
  45.                 {
  46.                     string subS = "";
  47.                     int leftBracket = 0;    // 左括号数目
  48.                     int rightBracket = 0;    // 右括号数目
  49.                     while(idx < s.size())
  50.                     {
  51.                         char ch = s[idx];
  52.                         ++idx;
  53.                         subS += ch;
  54.                         if(s[idx] == '[')
  55.                             ++leftBracket;
  56.                         else if(s[idx] == ']')
  57.                         {
  58.                             ++rightBracket;
  59.                             // 若遍历到右括号，且遍历到的右括号数 == 左括号数，则退出当前循环
  60.                             if(leftBracket == rightBracket)
  61.                                 break;
  62.                         };
  63.                     }
  64.                     // 递归解码 k_2[encoded_string_2]，并加到 curStr 后面
  65.                     curStr += decodeString(subS);
  66.                 }
  67.                 ++idx;
  68.             }
  69.             // 2.4 跳过 "]"
  70.             if(s[idx] == ']')
  71.                 ++idx;
  72.             // 2.5 将当前的 curStr 重复 number 次
  73.             result += repeatStringKTimes(curStr, number);
  74.         }
  75.         return result;
  76.     }
  77. };

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(N)：取决于递归深度，即字符串 s 中括号套括号的最大深度，最坏情况下为 O(N)，eg. 2[2[2[a]]]

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：6.2 MB, 在所有 C++ 提交中击败了 93.27% 的用户

解法二：辅助栈法

本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

核心思路就是用两个栈分别保存字符串和数字（重复次数），如果遇到 "[" 则入栈，遇到 "]" 则出栈

  1. class Solution {
  2. public:
  3.     string decodeString(string s) {
  4.         // 辅助栈
  5.         stack<string> resultStack;    // 存储字符串
  6.         stack<int> numberStack;        // 存储数字（重复次数）
  7.         string result = "";            // 结果字符串
  8.         int number = 0;                // 数字（重复次数）
  9.         // 遍历字符串 s 中的每个字符 s[i]
  10.         for(int i = 0; i < s.size(); ++i)
  11.         {
  12.             char ch = s[i];
  13.             // case 1. 若当前字符为字母，则添加到 result 尾部
  14.             if(ch >= 'a' && ch <= 'z')
  15.                 result += ch;
  16.             // case 2. 若当前字符为数字，则更新 number
  17.             else if(ch >= '0' && ch <= '9')
  18.                 number = number * 10 + ch - '0';
  19.             // case 3. 若当前是左括号，则将当前的 result 和 number 压入栈中，并重新初始化
  20.             else if(ch == '[')
  21.             {
  22.                 resultStack.push(result);    // 将当前的 result 压入栈
  23.                 numberStack.push(number);    // 将当前的 number 压入栈
  24.                 result = "";                // 将 result 清空
  25.                 number = 0;                    // 将 number 清零
  26.             }
  27.             // case 4. 若当前是右括号，则从栈中弹出之前的 result 和 number，来拼接字符串
  28.             else if(ch == ']')
  29.             {
  30.                 string lastResult = resultStack.top();    // 之前的字符串
  31.                 resultStack.pop();
  32.                 int lastNumber = numberStack.top();        // 代表当前字符串需要重复的次数
  33.                 numberStack.pop();
  35.                 // 将当前字符串重复 lastNumber 次，拼接到之前的字符串之后
  36.                 for(int j = 0; j < lastNumber; ++j)
  37.                     lastResult += result;
  38.                 result = lastResult;        // 更新当前字符串
  39.             }
  40.         }
  41.         return result;
  42.     }
  43. };

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 O(N)：一次遍历 s
  • 空间复杂度 O(N)：辅助栈大小取决于字符串 s 中括号套括号的最大深度，最坏情况下为 O(N)，eg. 2[2[2[a]]]
  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：6.4 MB, 在所有 C++ 提交中击败了 45.55% 的用户

解法三：递归法

  1. class Solution {
  2. private:
  3.     int end = 0;    // dfs 递归函数返回时遍历到的下标
  4.     // 递归函数定义：从下标 start 开始解码字符串 s，并返回解码后的字符串，返回时更新索引 end
  5.     string dfs(string s, int start)
  6.     {
  7.         string result = "";        // 解码后的结果字符串
  8.         int number = 0;            // 代表要重复的次数
  9.         int idx = start;        // 下标
  10.         // 遍历字符串
  11.         while(idx < s.size())
  12.         {
  13.             char ch = s[idx];
  15.             // case 1：如果当前字符是字母，则添加到 result 尾部
  16.             if(ch >= 'a' && ch <= 'z')
  17.                 result += ch;
  18.             // case 2：如果当前字符是数字，则更新 number
  19.             else if(ch >= '0' && ch <= '9')
  20.                 number = number * 10 + ch - '0';
  21.             // case 3：如果当前字符是 "["，则开启新一层递归，并拼接
  22.             else if(ch == '[')
  23.             {
  24.                 // 递归得到括号里面解码后的字符串
  25.                 string subStr = dfs(s, idx + 1);
  26.                 // 将 subStr 重复 number 次，添加到 result 尾部
  27.                 // 同时 number 清零
  28.                 while(number > 0)
  29.                 {
  30.                     result += subStr;
  31.                     --number;
  32.                 }
  33.                 // 更新下标为上面递归函数遍历到的最后一个字符的位置
  34.                 idx = end;
  35.             }
  36.             // case 4：如果当前字符是 "]"，则触发递归结束条件
  37.             // 用 end 记录当前访问到的下标，并返回本次递归得到的字符串 result
  38.             else if(ch == ']')
  39.             {
  40.                 end = idx;
  41.                 return result;
  42.             }
  44.             // 准备遍历下一个字符
  45.             ++idx;
  46.         }
  47.         end = idx;        // 这里写不写都行
  48.         return result;
  49.     }
  50. public:
  51.     string decodeString(string s) {
  52.         return dfs(s, 0);
  53.     }
  54. };

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 O(N)：递归返回的时候会更新当前已遍历到的下标 end，因此实际还是一次遍历 s
  • 空间复杂度 O(N)：递归深度（递归栈空间复杂度）取决于字符串 s 中括号套括号的最大深度，最坏情况下为 O(N)，eg. 2[2[2[a]]]
  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：6.2 MB, 在所有 C++ 提交中击败了95.86% 的用户