[LeetCode] Decode String

https://leetcode.com/problems/decode-string/description/?envType=study-plan-v2&envId=leetcode-75

 

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"
 

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

---

 

복호화된 문자열을 리턴하는 문제
암호화 규칙은 k[string]인데, 대괄호 내 string은 정확히 k번 반복된다.(k는 양수)
ex. 3[a] -> aaa

근데 이제 중첩도 가능함.... 3[a2[c]] -> 3[acc] -> accaccacc 이렇게... 

input string은 언제나 유효하다고 가정한다. 
-> 공백이 없고, 대괄호는 언제나 잘 열고 닫혀 있다 등등.
반복할 문자열에는 어떤 숫자도 포함되어 있지 않으며, 단순히 문자를 반복할 횟수만 적혀 있을 뿐이다.

 

var decodeString = function(s) {
    const arr = [...s];
    let result = "";
    let num = "";
    let str = "";
    let inSquare = false;
    for(let char of arr){
        if(!isNaN(char)){
            num += char;
            continue;
        }
        if(char === '['){
            str = "";
            inSquare = true;
            continue;
        }
        if(char === ']'){
            result += str.repeat(parseInt(num));
            num = "";
            str = "";
            inSquare = false;
            continue;
        }
        if(char !== '[' && char !== ']'){
            if(inSquare){
                str += char;
            }else{
                result += char;
            }
            continue;
        }
    }
    return result;

};

 

처음에는 단순히 이렇게 풀었는데, 이런 경우 중첩된 대괄호를 커버할 수가 없다는 단점이 있었다.

머리를 싸매다가.. 대괄호의 위치를 갖는 이중 배열을 만들어서 풀어볼까 하고 시도도 해보고,

이것저것 트라이하다가 discussion에서 누군가의 댓글에서 힌트를 얻었다.

 

#Simple advise! We adding each char to stack till we get ], 
#in this case, we can start decoding by taking last values from stack.

 

아무튼 결국 풀어냄ㅠ.. 스택을 이용해야 한다는 걸 알아도 푸는 게 쉽지 않다ㅋㅋㅋㅋ

 

var decodeString = function(s) {
    const arr = [...s];
    let num = "";
    let nums = [];
    let str = "";
    let strs = [];

    for(let i=0; i<s.length; i++){
        if(!isNaN(s[i])){
            num += s[i];
        }else if(s[i] == '['){
            nums.push(parseInt(num));
            strs.push(str);
            num = "";
            str = "";
        }else if(s[i] == ']'){
            let repeatCount = nums.pop();
            let prevStr = strs.pop() ?? ""
            str = prevStr + str.repeat(repeatCount);
            continue;
        }else{
            str += s[i];
        }
    }
    return str;

};

 

대괄호의 열고 닫음을 마주칠 때마다 반복횟수와 반복 string을 스택으로 저장한다.

닫을 때마다 맨 마지막 string을 맨 마지막 반복횟수만큼 반복한 뒤 str에 저장한다.

원리는 단순함... ㅋㅋ 근데 머리로 떠올리는게 쉽지 않은 것 같다.

 

스택 니가 뭔데... 

저도요.