問(wèn)題描述

該問(wèn)題，用最簡(jiǎn)單的語(yǔ)言描述，就是將通過(guò)一定規(guī)則壓縮的字符解壓為原始字符，舉例如下圖示：

求解思路

按照人最直覺(jué)的想法，解壓思路如下：

1. 如果不存在中括號(hào)，就直接返回結(jié)果；
2. 如果由中括號(hào)一層層包起來(lái)的，就是一層層往里剝；
3. 如果有多個(gè)獨(dú)立的中括號(hào)結(jié)構(gòu)，就每個(gè)中括號(hào)內(nèi)容分別解壓，結(jié)果加起來(lái)；

上面的思路，本質(zhì)上是遞歸。

代碼實(shí)現(xiàn)

根據(jù)上述思路，用c++編寫(xiě)代碼：

    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));}

實(shí)現(xiàn)結(jié)果

上面代碼運(yùn)行后，34個(gè)算例全部測(cè)試通過(guò)，耗時(shí)2毫秒，空間10.61M，見(jiàn)下圖：

優(yōu)化思路

上述代碼中，存在重復(fù)計(jì)算。比如，針對(duì)算例

開(kāi)始計(jì)算了一次’]‘所在位置，為3，然后將字符串拆分為"3[a]“和2"bc”，然后在對(duì)"3[a]"進(jìn)行解碼時(shí)要重新計(jì)算同一個(gè)’]'的位置。

為了避免重復(fù)計(jì)算，選擇從內(nèi)往外解碼，具體思路如下：
定義數(shù)字棧indexList，字符串棧strList，緩存字符串midStr，結(jié)果字符串result；

1. 匹配’[‘字符，識(shí)別’['前面的字符串和數(shù)字；
2. 將緩存中的字符串midStr與識(shí)別的字符串相加，字符串和數(shù)字分別入棧，清空緩存中的字符；
3. 匹配’]‘字符，識(shí)別’]'前面的字符串；
4. 將緩存中的字符串midStr與識(shí)別的字符串相加，得到字符串tempStr；
5. 將數(shù)字棧和字符串棧分別出棧，出棧的元素分別為lastNum、lastStr。lastNum數(shù)量的tempStr接長(zhǎng)，并在前面加上lastStr，得到新的字符串currentStr；
6. 將currentStr存入緩存；
7. 如果數(shù)字棧中元素個(gè)數(shù)為0，將緩存中的字符串接長(zhǎng)到結(jié)果字符串result中，清空緩存midStr；
8. 如果最后一個(gè)’]'后面還有字符，將剩余字符添加到結(jié)果。

該思路，取消遞歸，改用棧實(shí)現(xiàn)(不需要遞歸，所以能直接在已有結(jié)果上解碼，不需要遞歸后重新查找位置)；同時(shí)增加一個(gè)midStr用于，解碼過(guò)程中信息傳遞。該思路最大限度避免了重復(fù)計(jì)算。

優(yōu)化后的代碼

    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;}

優(yōu)化結(jié)果

優(yōu)化后，34個(gè)算例全部通過(guò)，運(yùn)行時(shí)間0毫秒，消耗內(nèi)存9.78M，見(jiàn)下圖：

結(jié)果對(duì)比可知，優(yōu)化后，運(yùn)行時(shí)間減少了超過(guò)75%，空間有所減少，復(fù)雜度不變。