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