題目鏈接：
https://www.lintcode.com/problem/282/description?_from=collection&fromId=208

描述：
小Q想要給他的朋友發(fā)送一個(gè)神秘字符串，但是他發(fā)現(xiàn)字符串太長(zhǎng)了，于是小Q發(fā)明了一種壓縮算法對(duì)字符串中重復(fù)的部分進(jìn)行了壓縮，對(duì)于字符串中連續(xù)的m個(gè)相同字符串S將會(huì)壓縮為[m|S](m為一個(gè)整數(shù)且1<=m<=100)，例如字符串ABCABCABC將會(huì)被壓縮為[3|ABC]，現(xiàn)在小A收到了小Q發(fā)送過來的字符串，你能幫助他進(jìn)行解壓縮么？

數(shù)據(jù)范圍：
1、S的長(zhǎng)度<=1000;
2、S僅包含大寫字母、[、]、|;
3、解壓后的字符串長(zhǎng)度不超過;
4、壓縮遞歸層數(shù)不超過10層;

樣例：
輸入 : "HG[3|B[2|CA]]F"
輸出 : "HGBCACABCACABCACAF"
解釋 : HG[3|B[2|CA]]F ??> HG[3|BCACA]F ??> HGBCACABCACABCACAF

解題思路：
首先先將最內(nèi)層的方括號(hào)打開，如果我們找左括號(hào)想要找到最內(nèi)層不太容易，所以我們應(yīng)該先找右括號(hào)，第一個(gè)右括號(hào)肯定是最內(nèi)層的壓縮字符串，然后再在循環(huán)里從該右括號(hào)往前找'|'和左括號(hào)，然后將其解壓，我的思路是將原字符串分成兩部分s1和s2，然后將括號(hào)內(nèi)壓縮的字符串解壓后構(gòu)造成s3，最后將其拼接，一直這樣遍歷到原字符串結(jié)束。

具體代碼如下：

創(chuàng)新互聯(lián)是專業(yè)的大興安嶺網(wǎng)站建設(shè)公司，大興安嶺接單;提供成都做網(wǎng)站、成都網(wǎng)站制作,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行大興安嶺網(wǎng)站開發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

class Solution {
public:
/**
     * @param Message: the string xiao Q sent to xiao A.
     * @return: the string after decompress
*/

    string DecompressString(string &Message) {
string s1, s2;  　　　　//s1:前半串 s2：后半串
string s3 = "";　　　　 //部分解壓后的字符串
int index = 0;　　　　  //'|'的位置
        code:
for (int i = 0; i < Message.length(); i++)　　　//遍歷右括號(hào)
            {
if (Message[i] == ']')
                {
                    s2= Message.substr(i + 1, Message.length() - i - 1);　　　//截取后半段字符串
for (int j = i; ; j--)　　　　　　　　　　　　　　　　　　　　　 //往前找'|'和'['
                    {
string ts = "", tss = "";　　　　　　　　　　　　　　　　　 //ts：壓縮字符串的個(gè)數(shù),壓縮的字符串
                        if (Message[j] == '|')index = j;
if (Message[j] == '[')
                        {
                            s1= Message.substr(0, j);　　　　　　　　　　　　　　 //截取前半段字符串
for (int k = j + 1; k < index; k++)ts += Message[k];
int t = stoi(ts, 0, 10);　　　　　　　　　　　　　　　　//將string型轉(zhuǎn)為int型
for (int l = index + 1; l < i; l++)tss += Message[l];
for (int p = 0; p < t; p++)s3 += tss;　　　　　　　　//構(gòu)造s3
                            Message= s1 + s3 + s2;　　　　　　　　　　　　　　　　 //拼接部分解壓后的字符串
                            j+= s3.length() - (j - i);　　　　　　　　　　　　　  //將j、i的位置放到新串上
                            i= j;
                            s3= "";　　　　　　　　　　　　　　　　　　　　　　　　　 //清空s3
goto code;　　　　　　　　　　　　　　　　　　　　　　　　 //退出第一輪解壓
                        }
                    }
                }
            }
return Message;
    }
};

當(dāng)前題目：LintCode-282 &#183; 解壓字符串-題解
文章路徑：http://chinadenli.net/article0/dsogoio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、微信小程序、網(wǎng)站設(shè)計(jì)、標(biāo)簽優(yōu)化、定制網(wǎng)站、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)