leetcode394字符串解码(回溯|栈)「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

题解
注意可能会出来[[]]嵌套的情况

回溯

class Solution { 

public:
stringstream ss;
string chartostring(char a){ 

string t = "";
t.append(1,a);
return t;
}
string dfs(int l,int r,string &s){ 

if(l == r)return chartostring(s[l]);
if(l > r)return "";
string t = "";
if(s[l] >= 'a' && s[l] <= 'z'){ 

t.append(1,s[l]);
return t += dfs(l + 1,r,s);
}
else{ 

int k = l;
while(k < s.size() && s[k] >= '0' && s[k] <= '9')k ++;
ss.clear();
ss << s.substr(l,k - l);
int num;
ss >> num;
int rr = k + 1,cnt = 1;
while(cnt != 0){ 

if(s[rr] == '[')cnt ++;
else if(s[rr] == ']')cnt --;
rr ++;
}
rr --;
string tt = dfs(k + 1,rr - 1,s);
for(int i = 0;i < num;i ++)t.append(tt);
t += dfs(rr + 1,r,s);
}
cout<<t<<endl;
return t;
}
string decodeString(string s) { 

string res = dfs(0,s.size() - 1,s);
return res;
}
};

class Solution { 

public:
string chartostring(char x){ 

string t = "";
t.append(1,x);
return t;
}
bool isalpha(char x){ 

return x >= 'a' && x <= 'z';
}
bool isnum(char x){ 

return x >= '0' && x <= '9';
}
string decodeString(string s) { 

stack<string>stk;
stringstream ss;
string res = "";
int num = 0;
for(int i = 0;i < s.size();i ++){ 

if(isalpha(s[i]) || s[i] == '['){ 

stk.push(chartostring(s[i]));
}
else if(isnum(s[i])){ 

int j = i;
while(j < s.size() && isnum(s[j]))j ++;
stk.push(s.substr(i,j - i));
i = j - 1;
}else{ 

string t = "";
while(stk.top() != "["){ 

t.insert(0,stk.top());
stk.pop();
}
stk.pop();
ss.clear();
ss << stk.top();
ss >> num;
stk.pop();
string tt = "";
for(int i = 0;i < num;i ++){ 

tt.insert(0,t);
}
stk.push(tt);
}
}
while(!stk.empty()){ 

res.insert(0,stk.top());
stk.pop();
}
return res;
}
};