[Leetcode] 394. Decode String

문제

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 <= 30s 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].

 

풀이

[substring] 안의 [substring]이 있는 경우도 다루기 위해 recursion을 사용한다.

 

먼저 recursion을 위한 helper function을 만들고 end condition을 생각해본다.

recursion은 [] 안에 아무런 숫자가 없고 그냥 문자만 있을때 멈추고 그 안의 문자를 리턴한다.

 

큰 while loop 안에서  ']'전의 문자만 다루도록 할 때, 차근차근 필요한 요소를 구해준다.

시작하는 숫자를 구해주고 (이때 300까지 나올 수 있는 걸 고려함), '['를 스킵하고, 안의 문자를 구해주고 (recursion), 문자를 n번 반복한 뒤,  ']'를 스킵하고, 리턴한다.

 

이 때, 항상 인덱스 숫자를 트랙해야하고 인덱스 숫자는 계속 바뀌기 때문에 helper function안에서 pointer(*i)로 써야한다.

 

코드

#define MAX_SIZE 10000
char* decodeStringHelper(char* s, int* i) {
    char* result = (char*)malloc(MAX_SIZE * sizeof(char));
    int result_len = 0;

    while(s[*i]!='\0' && s[*i] != ']') {
        if(!isdigit(s[*i])) { // recursion end condition = no number appearing in substring
            result[result_len++] = s[(*i)++];
        } else {
            // find number (n)
            int n = 0;
            while(isdigit(s[*i])) {
                if(n==0) {
                    n = s[*i] - '0';
                } else {
                    n = n*10+(s[*i]-'0');
                }
                (*i)++;
            }

            // skip '['
            (*i)++;

            // find & add substring to result
            char* substring = decodeStringHelper(s, i);

            for(int i=0; i<n; i++) { // repeat n times
                strcpy(result+result_len, substring);
                result_len += strlen(substring);
            }

            // skip ']'
            (*i)++;

            free(substring);
        }
    }
    result[result_len] = '\0';
    return result;
    
}

char* decodeString(char* s) {
    int i = 0;
    return decodeStringHelper(s, &i);
}