LintCode-282 · 解壓字串-題解-有解無憂

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

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

資料范圍：
1、S的長度<=1000;
2、S僅包含大寫字母、[、]、|;
3、解壓后的字串長度不超過100000;
4、壓縮遞回層數不超過10層;

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

解題思路：
首先先將最內層的方括號打開，如果我們找左括號想要找到最內層不太容易，所以我們應該先找右括號，第一個右括號肯定是最內層的壓縮字串，然后再在回圈里從該右括號往前找'|'和左括號，然后將其解壓，我的思路是將原字串分成兩部分s1和s2，然后將括號內壓縮的字串解壓后構造成s3，最后將其拼接，一直這樣遍歷到原字串結束，

具體代碼如下：

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++)　　　//遍歷右括號
            {
                if (Message[i] == ']')
                {
                    s2 = Message.substr(i + 1, Message.length() - i - 1);　　　//截取后半段字串
                    for (int j = i; ; j--)　　　　　　　　　　　　　　　　　　　　　 //往前找'|'和'['
                    {
                        string ts = "", tss = "";　　　　　　　　　　　　　　　　　 //ts：壓縮字串的個數,壓縮的字串
                        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型轉為int型
                            for (int l = index + 1; l < i; l++)tss += Message[l];
                            for (int p = 0; p < t; p++)s3 += tss;　　　　　　　　//構造s3
                            Message = s1 + s3 + s2;　　　　　　　　　　　　　　　　 //拼接部分解壓后的字串
                            j += s3.length() - (j - i);　　　　　　　　　　　　　  //將j、i的位置放到新串上
                            i = j;
                            s3 = "";　　　　　　　　　　　　　　　　　　　　　　　　　 //清空s3
                            goto code;　　　　　　　　　　　　　　　　　　　　　　　　 //退出第一輪解壓
                        }
                    }
                }
            }
        return Message;
    }
};

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/421623.html

標籤：其他

上一篇：Java 實作音頻添加自定義時長靜音（附代碼） | Java工具類

下一篇：基于Redis&MySQL介面冪等性設計