[LeetCode] 394 Decode String (Week 8, No.4)

Description

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].

---

풀이

숫자 스택과 문자 스택을 만든다.
문자열의 한 문자씩 본다.
현재 문자를 curLetter에 저장해둔다.
curLetter가 문자인지, 숫자인지, 괄호인지 보고 각각의 문장을 수행한다.

• 숫자일 경우,
  계속 숫자 스트링빌더에 더한다.
  인덱스를 증가시킨다.
• 여는 괄호일 경우,
  숫자 스트링빌더를 문자로 만든 뒤 숫자 스택에 넣는다.
  결과 스트링빌더를 문자 스택에 넣는다.
  문자와 결과 스트링빌더를 새로 초기화한다.
  인덱스를 증가시킨다.
• 닫는 괄호일 경우,
  문자 스택에서 꺼내와 새로운 임시 스트링빌더에 저장한다.
  숫자 스택에서 숫자를 꺼내온다.
  임시 스트링빌더에 꺼낸 숫자만큼 결과 스트링빌더를 반복하여 더한다.
  결과 스트링빌더를 임시 스트링빌더로 만든다.
  인덱스를 더한다.
• 문자일 경우,
  문자를 결과 스트링빌더에 더하고 인덱스를 증가시킨다.

간략하게,
숫자가 나오면 -> 여는 괄호가 나올 때까지 모아둔다.
문자가 나오면 -> 현재 문자를 모은다.
여는 괄호가 나오면 -> 모은 숫자와 문자를 각 스택에 넣는다. 그리고 모으던 스트링 빌더들을 초기화한다.
닫는 괄호가 나오면 -> 문자 스택에서 꺼내와 임시 스트링빌더에 넣고, 숫자 스택에서 꺼낸 수만큼 저장된 문자를 반복하여 임시 스트링빌더에 넣는다.
다 넣으면 결과에 임시 스트링빌더를 넣는다.

결과 스트링빌더를 문자로 바꾸어 반환한다.

---

코드

class Solution {
    public String decodeString(String s) {
        Stack<String> strStack = new Stack<>();
        Stack<Integer> numStack = new Stack<>();
        StringBuilder res = new StringBuilder();
        StringBuilder numSb = new StringBuilder();

        int idx = 0;
        while (idx < s.length()) {
            char curLetter = s.charAt(idx);
            if (Character.isDigit(curLetter)) {
                numSb.append(curLetter);
                idx++;
            } else if (curLetter == '[') {
                numStack.push(Integer.parseInt(numSb.toString()));
                strStack.push(res.toString());
                numSb = new StringBuilder();
                res = new StringBuilder();
                idx++;
            } else if (curLetter == ']') {
                StringBuilder temp = new StringBuilder(strStack.pop());
                int repeatTimes = numStack.pop();
                for (int i = 0; i < repeatTimes; i++) {
                    temp.append(res);
                }
                res = temp;
                idx++;
            } else {
                res.append(s.charAt(idx++));
            }
        }
        return res.toString();
    }
}