leetcode菜狗入門|394.文字列復号
13528 ワード
文字列復号
タイトルの説明
符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、k[encoded_string]であり、カッコ内のencoded_を表すstringはちょうどk回繰り返します.注意kは正の整数であることを保証する.
入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.
また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.
例:s = "3[a]2[bc]", "aaabcbc".
s = "3[a2[c]]", "accaccacc".
s = "2[abc]3[cd]ef", "abcabccdcdcdef".
問題を解く構想.
2つのスタック、1つのデジタルスタック、1つの文字スタック、デジタルスタックの格納倍数を作成します.文字スタックが「」に遭遇すると、「[」に遭遇するまでスタックを出て、デジタルスタックはスタックを突き出して、スタックの文字列を倍数で変換して、文字スタックが空でない場合は文字スタックに入れて、さもなくばansの後でつなぎ合わせて、文字スタックとデジタルスタックがすべて空である場合、現在の文字を直接ansの後でつなぎ合わせます
コード#コード#
class Solution {
public:
string decodeString(string s) {
stack<int> count;
stack<char> str;
string ans = "";
if(s.length() == 0) return ans;
int i = 0;
int num = -1;
while(i < s.length()){
while(s[i] >= '0' && s[i] <= '9' && i < s.length()){
if(num == -1)
num = s[i] - '0';
else
num = num*10 + (s[i]-'0');
i++;
}
if(num != -1){
count.push(num);
num = -1;
}
if(count.empty() && str.empty()){
ans.push_back(s[i]);
i++;
continue;
}
if(s[i] != ']'){
str.push(s[i]);
i++;
}
else{
string temp = "";
while(str.top() != '['){
temp.push_back(str.top());
str.pop();
}
str.pop();
reverse(temp.begin(), temp.end());
int beishu = count.top();
//cout<
count.pop();
string cur = temp;
for(int j = 1; j <beishu; j++){
temp += cur;
}
if(str.empty())
ans += temp;
else{
for(int j = 0; j < temp.length(); j++){
str.push(temp[j]);
}
}
i++;
}
}
return ans;
}
};
s = "3[a]2[bc]", "aaabcbc".
s = "3[a2[c]]", "accaccacc".
s = "2[abc]3[cd]ef", "abcabccdcdcdef".
class Solution {
public:
string decodeString(string s) {
stack<int> count;
stack<char> str;
string ans = "";
if(s.length() == 0) return ans;
int i = 0;
int num = -1;
while(i < s.length()){
while(s[i] >= '0' && s[i] <= '9' && i < s.length()){
if(num == -1)
num = s[i] - '0';
else
num = num*10 + (s[i]-'0');
i++;
}
if(num != -1){
count.push(num);
num = -1;
}
if(count.empty() && str.empty()){
ans.push_back(s[i]);
i++;
continue;
}
if(s[i] != ']'){
str.push(s[i]);
i++;
}
else{
string temp = "";
while(str.top() != '['){
temp.push_back(str.top());
str.pop();
}
str.pop();
reverse(temp.begin(), temp.end());
int beishu = count.top();
//cout<
count.pop();
string cur = temp;
for(int j = 1; j <beishu; j++){
temp += cur;
}
if(str.empty())
ans += temp;
else{
for(int j = 0; j < temp.length(); j++){
str.push(temp[j]);
}
}
i++;
}
}
return ans;
}
};