LeetCode 394-文字列復号
1839 ワード
タイトル:
符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、k[encoded_string]であり、カッコ内のencoded_を表すstringはちょうどk回繰り返します.注意kは正の整数であることを保証する.
入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.
また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.
例:
s="3[a]2[bc],"aaabcbc"を返す.s="3[a 2[c]",は"accaccacc"を返す.s="2[abc]3[cd]ef"、abcabccdcdefを返す.
考え方:
ここではスタックに入る要素が何なのかを理解しなければなりません.ここは左から右へ、中から外への過程だからです.2[bc]を操作する場合,bc以前の文字列の接合結果とbcに対する操作回数(すなわち2)を知る必要がある.では、pairの構造を使用することができる2つの情報を格納します.次は状況を分けて討論する.文字が数字の場合、timesで数字の大きさを記録します.文字が'['の場合、新しい復号が間もなく始まることを意味するので、古いデータresおよび新しい復号が行われる回数をpair形式でスタックに格納するとともに、resを空にし、timesを0にして、後の復号操作を容易にする.文字が英字の場合、この一連の文字をresで格納する.文字が'''の場合、現在の文字列の結果を計算することができる.前のスタックのヘッダ要素情報を取り出し、接合する必要があります.
https://leetcode-cn.com/problems/decode-string/solution/zhi-xing-yong-shi-0-ms-zai-suo-you-c-ti-jiao-zh-47/
コード:
class Solution {
private:
string repeatStr(string T, int times)
{
string ans = "";
for (int i = 0; i < times; i++)
{
ans += T;
}
return ans;
}
public:
string decodeString(string& s) {
//int len = s.size();
int times = 0;
string res = "";
typedef pair pa;
vector>st;
for (auto c : s)
{
if (c >= '0' && c <= '9') times = times * 10 + (c - '0');
else if (c == '[')
{
st.push_back(pa(times, res));
res = "";
times = 0;
}
else if(c==']')
{
pa temp = st[st.size()-1];
st.pop_back();
res = temp.second + ((temp.first==0)? "" : repeatStr(res,temp.first));
}
else
{
res += c;
}
}
return res;
}
};