[leetcode #394] Decode String

Problem

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Example 4:

Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"

Constraints:

・ 1 <= s.length <= 30
・ s consists of lowercase English letters, digits, and square brackets '[]'.
・ s is guaranteed to be a valid input.
・ All the integers in s are in the range [1, 300].

Idea

Stack을 이용해서 풀다가 시간이 많이 걸려 Discussion에 Solution을 참조하였다😱

'[]' 사이의 문자열은 '[]' 앞의 숫자만큼 반복이 되기 때문에 '['가 나왔을 때 Stack에 넣고 ']'가 나왔을 때 Stack에서 빼는 방법으로 구현해보려고 했으나 쉽지 않았다. 이 문제를 푸는 더 좋은 방법은 내부 stack을 이용하는 것이다.

내부 stack을 이용한다는 것은 함수를 substring을 인자로 넣어 재귀적으로 호출한다는 것을 의미한다. 꼭 substring이 아니더라도 class의 멤버 변수를 이용하면 substring을 넣는 것처럼 구현할 수 있다.

우선 주어진 문자열의 index인 pos를 멤버 변수로 만든다. pos는 각 문자를 탐색하면서 1씩 increment된다. 현재 문자에 따라 처리하는 게 달라지는데, 일반 문자는 buffer에 append시키고, 숫자일 경우는 repeat할 수를 계산해서 저장한다. ']'가 나올 경우 break하면 된다.

']'가 나올 때 break하면 '[]'를 한 번만 처리하고 이후의 문자열은 무시하는 것이 아니냐고 생각할 수 있는데 그렇지 않다. '['가 나왔을 때 pos을 1 올린 뒤 decodeString을 재귀호출한 후 리턴한 문자열을 append시키고, repeat를 0으로 초기화한다. 이렇게 하면 재귀함수에서 ']'가 나왔을 때 break 되며, 재귀함수를 호출한 쪽에서 '['를 처리한 이후 pos을 1 올리기 때문에 ']' 이후의 문자로 이동하기 때문이다.

즉, '['가 나왔을 때 repeat만큼 재귀함수가 리턴한 문자열을 append시키면 되고, 나머지 경우에는 문자를 하나씩 append시키면 된다. '[]'의 처리는 전부 재귀함수에 맡기는 것이다.

이렇게 풀 수 있을 거란 생각은 전혀 하지 못 했는데, 풀이를 보고 왜 이런 생각을 못 했는지 반성하게 되었다 🥲

Solution

class Solution {
    private int pos = 0;

    public String decodeString(String s) {
        StringBuffer stringBuffer = new StringBuffer();    
        int repeat = 0;

        while (pos < s.length()) {
            char c = s.charAt(pos);

            if (c == '[') {
                pos++;
                String substr = decodeString(s);
                for (int i=0; i < repeat; i++)
                    stringBuffer.append(substr);
                repeat = 0;
            } else if (c >= '0' && c <= '9') {
                repeat = repeat * 10 + (c - '0');
            } else if (c == ']') {
                break;
            } else {
                stringBuffer.append(c);
            }
            pos++;
        }

        return stringBuffer.toString();
    }
}

Reference

https://leetcode.com/problems/decode-string/