[leetcode] 394。文字列のデコード
394 Decode String
説明
エンコードされた文字列を指定して、デコードされた文字列を返します。
エンコード規則は次のとおりです。k[encoded_string]。角括弧内のencoded_stringは正確にk回繰り返されます。 kは正の整数であることが保証されていることに注意してください。
入力文字列は常に有効であると想定できます。余分な空白や角かっこは整形式ではありません。
さらに、元のデータには数字が含まれておらず、数字はそれらの繰り返し番号kのみであると想定できます。たとえば、3aや2 [4]のような入力はありません。
例:
s = '3[a]2[bc]', return 'aaabcbc'. s = '3[a2[c]]', return 'accaccacc'. s = '2[abc]3[cd]ef', return 'abcabccdcdcdef'.
分析
タイトルの意味は次のとおりです。ルールに従って文字列をデコードするように求める文字列を指定します。
- これは再帰的なソリューションです。
- まず、文字の場合は直接解像度に結合します。そうでない場合は、数字の左角かっこである可能性があります。
- 数値の場合、最初に数値の値を計算します。数値の後に左角かっこを付ける必要があります。次にそれをスキップし、再帰後に左角かっこ内の文字列を再帰的にデコードします。
- sの終わりまで、または右角かっこを満たすために、戻り条件を分析します。したがって、i ++、つまり、右角かっこをスキップするか、最後に移動して、t * count回の文字列をresに追加します。に。
コード
public: string decodeString(string s) { int i=0 return decode(s,i) } string decode(string s,int &i){ int n=s.length() string res='' while(i='0'&&s[i]<='9'){ count=count*10+s[i]-'0' i++ } i++ string t=decode(s,i) i++ while(count--){ res+=t } } } return res } }