394. Decode String

Decode String - LeetCode

 

주어진 인코딩된 문자열을 디코딩하여 반환합니다.
인코딩 규칙은 다음과 같습니다: k[encoded_string], 여기서 대괄호 내의 encoded_string은 정확히 k번 반복됩니다. 여기서 k는 양의 정수임이 보장됩니다.
입력 문자열이 항상 유효하다고 가정할 수 있습니다. 추가적인 공백이 없으며, 대괄호가 올바르게 구성되었고, 원본 데이터에 숫자가 포함되지 않으며 숫자는 반복 횟수 k에만 사용됩니다. 예를 들어 3a 또는 2[4]와 같은 입력은 없습니다.
테스트 케이스는 결과 문자열의 길이가 105를 넘지 않도록 생성됩니다.

 

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; there are 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 will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 105.

 

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"

 

문제 요약: 

주어진 인코딩된 문자열 s를 디코딩하여 원래 문자열로 반환합니다. 인코딩 규칙은 다음과 같습니다:

• 숫자 k 다음에 대괄호 [ 가 나옵니다.
• 대괄호 안의 문자열을 k번 반복하여 구성합니다.
• 디코딩된 문자열을 반환합니다.

풀이과정:

1. 스택을 사용하여 숫자와 문자열을 처리합니다. 두 개의 스택을 사용합니다. 하나는 숫자를 저장하는 numStack, 다른 하나는 문자열을 저장하는 strStack입니다.
2. 문자열을 순회하면서 숫자와 대괄호를 처리합니다. 숫자인 경우 num 변수에 숫자를 저장하고, 대괄호가 열리면 num을 numStack에 넣고, 현재 문자열을 strStack에 넣어 초기화합니다.
3. 대괄호가 닫히면, numStack에서 숫자를 꺼내어 반복 횟수를 얻습니다. 그리고 현재 문자열 currentStr을 해당 횟수만큼 반복하여 새로운 문자열 newStr을 생성합니다.
4. newStr을 strStack에서 꺼낸 이전 문자열에 추가하고, 다시 currentStr을 업데이트합니다.
5. 숫자도 대괄호도 아닌 경우에는 현재 문자열 currentStr에 해당 문자를 추가합니다.
6. 모든 문자를 처리한 후 currentStr을 반환하면 디코딩된 문자열이 됩니다.

class Solution {
    public String decodeString(String s) {
        Stack<Integer> stkNum = new Stack<>();
        Stack<String> stkStr = new Stack<>();
        
        int tmpNum = 0;
        String tmpStr = "";

        for(char c: s.toCharArray()){
            if(Character.isDigit(c)){
                tmpNum = tmpNum *10 + Character.getNumericValue(c);
            }else if(c == '['){
                stkNum.push(tmpNum);
                stkStr.push(tmpStr);
                tmpNum = 0;
                tmpStr = "";
            }else if(c == ']'){
                int reNum = stkNum.pop();
                String reStr = stkStr.pop();

                for(int i = 0; i < reNum; i++){
                    reStr += tmpStr;
                }
                tmpStr = reStr;
            }else{
                tmpStr += c;
            }
        }
        return tmpStr;
    }
}