Matsushita's Blog

394. Decode String - Stackを使った解法 : Past Google Coding Interview

問題

leetcode.com

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

このように[]で囲まれた文字を直前の数字の数だけ繰り返しながら文字列を作って行く問題。

解法

これはStackを用いて解くことができる。用意するStackは以下の2つ。

  1. 繰り返す回数を保持しておくためのStack
  2. これまで作成した文字列を保持しておくためのStack

なぜStackを使用するのか

Stackの特徴は以下の通り。

  • pushにより要素を追加
  • popにより最新の要素を取り出す

今回の問題では、与えられる文字列の[]に着目すると入れ子構造になっている。文字列を繰り返す操作は、より深い階層の括弧が優先される。こういった場合Stackを使用することが有効である。Stackを使用することである階層の状態を保ったまま次の階層の処理を行うことができる。

ソースコード