LeetCode 2020-11-19: Decode String

Decode String (medium) の挑戦メモ。

問題の概要

• あるルールに則ってエンコードされた文字列を復元する
  • たとえば "3[a]2[bc]" であれば、a を 3 回繰り返し、そのあとに bc を 2 回繰り返した文字列 "aaabcbc" が復元結果となる
• ルール
  • エンコード文字列は 数値[文字列] で表現される
    • 数値の回数だけ「文字列」が繰り返される
  • エンコード文字列は入れ子にできる
    • "3[a2[c]]" を復元すると "3[acc]" → "accaccacc" となる

考え方

• これは再帰を使えば順当に解けますね
• 細かな速度パフォーマンスに配慮するために、復元中の文字列を StringBuilder で表現しつつ、入れ子の文字列の復元はその StringBuilder を参照させるようにしてみよう
• 実装 → submit → accept 👍
  • 0ms 達成 🎉

コード

class Solution {
    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        decodeRecursive(s, 0, result);
        return result.toString();
    }

    int decodeRecursive(String s, int index, StringBuilder sb) {
        while (index < s.length()) {
            char ch = s.charAt(index);
            if (ch <= '9') {
                int k = 0;
                do {
                    k = k * 10 + (ch - '0');
                } while ((ch = s.charAt(++index)) != '[');

                int repBegin = sb.length();
                index = decodeRecursive(s, index + 1, sb);
                int repEnd = sb.length();

                for (int j = 1; j < k; j++) {
                    sb.append(sb, repBegin, repEnd);
                }

            } else if (ch >= 'a') {
                sb.append(ch);
                index++;

            } else {  // ']'
                return index + 1;
            }
        }

        return index;
    }
}