当前位置：首页 > backend >正文

算法优化——394. 字符串解码

backend 2025/6/16 23:09:12

问题描述

该问题，用最简单的语言描述，就是将通过一定规则压缩的字符解压为原始字符，举例如下图示：
在这里插入图片描述

求解思路

按照人最直觉的想法，解压思路如下：

如果不存在中括号，就直接返回结果；
如果由中括号一层层包起来的，就是一层层往里剥；
如果有多个独立的中括号结构，就每个中括号内容分别解压，结果加起来；

上面的思路，本质上是递归。

代码实现

根据上述思路，用c++编写代码：

    string decodeString(string s) {string result;stack<int> indexList;int startIndex = -1;int endIndex = -1;for (int i = 0; i < s.length(); ++i) {if (s[i] == '[') {if (indexList.size() == 0)startIndex = i;indexList.push(i);} else if (s[i] == ']') {indexList.pop();if (indexList.size() == 0) {endIndex = i;break;}}}if (startIndex == -1)return s;if (endIndex == s.length() - 1) {string innerStr = decodeString(s.substr(startIndex + 1, endIndex - startIndex - 1));int leftIndex = 0;for (int i = 0; i < startIndex; ++i) {if (s[i] >= '0' && s[i] <= '9') {leftIndex = i;break;}}result = result + s.substr(0, leftIndex);int count = stoi(s.substr(leftIndex, startIndex - leftIndex));for (int i = 0; i < count; ++i) {result = result + innerStr;}return result;}return decodeString(s.substr(0, endIndex + 1)) +decodeString(s.substr(endIndex + 1));}

实现结果

上面代码运行后，34个算例全部测试通过，耗时2毫秒，空间10.61M，见下图：
在这里插入图片描述

优化思路

上述代码中，存在重复计算。比如，针对算例
在这里插入图片描述
开始计算了一次’]‘所在位置，为3，然后将字符串拆分为"3[a]“和2"bc”，然后在对"3[a]"进行解码时要重新计算同一个’]'的位置。

为了避免重复计算，选择从内往外解码，具体思路如下：
定义数字栈indexList，字符串栈strList，缓存字符串midStr，结果字符串result；

匹配’[‘字符，识别’['前面的字符串和数字；
将缓存中的字符串midStr与识别的字符串相加，字符串和数字分别入栈，清空缓存中的字符；
匹配’]‘字符，识别’]'前面的字符串；
将缓存中的字符串midStr与识别的字符串相加，得到字符串tempStr；
将数字栈和字符串栈分别出栈，出栈的元素分别为lastNum、lastStr。lastNum数量的tempStr接长，并在前面加上lastStr，得到新的字符串currentStr；
将currentStr存入缓存；
如果数字栈中元素个数为0，将缓存中的字符串接长到结果字符串result中，清空缓存midStr；
如果最后一个’]'后面还有字符，将剩余字符添加到结果。

该思路，取消递归，改用栈实现(不需要递归，所以能直接在已有结果上解码，不需要递归后重新查找位置)；同时增加一个midStr用于，解码过程中信息传递。该思路最大限度避免了重复计算。

优化后的代码

    pair<string, int> GetPairFromStr(string str) {int startIndex = -1;for (int i = 0; i < str.length(); ++i) {if (str[i] >= '0' && str[i] <= '9') {startIndex = i;break;}}if (startIndex == -1)return {str, 0};return {str.substr(0, startIndex), stoi(str.substr(startIndex))};}string decodeString(string s) {if (s.find('[') == string::npos)return s;stack<int> indexList;stack<string> strList;int startIndex = 0;string result;string midStr;for (int i = 0; i < s.length(); ++i) {if (s[i] == '[') {pair<string, int> tempPair =GetPairFromStr(s.substr(startIndex, i - startIndex));indexList.push(tempPair.second);strList.push(midStr + tempPair.first);midStr = "";startIndex = i + 1;} else if (s[i] == ']') {string tempStr = midStr + s.substr(startIndex, i - startIndex);string lastStr = strList.top();int lastNum = indexList.top();string currentStr = lastStr;for (int i = 0; i < lastNum; ++i) {currentStr = currentStr + tempStr;}indexList.pop();strList.pop();startIndex = i + 1;midStr = currentStr;if (indexList.size() == 0) {result = result + currentStr;midStr = "";}}}if (startIndex != s.length())result = result + s.substr(startIndex);return result;}