394. Decode String

문제링크: https://leetcode.com/problems/decode-string/description/

s로 압축된 문자열이 주어진다. 숫자[내용물] 로 압축된 부분은 내용물을 반복하는 것으로 압축되어있을 때 해독 결과를 결과로 반환해야 한다.

Solution

1. Recursion

괄호 사이의 반복해야 되는 구간은 똑같은 decodeString으로 동작한다. 따라서 괄호 속의 string을 똑같이 decodeString을 통해 푸는 재귀를 통해서 쉽게 구현할 수 있다.

Algorithm

• result에 결과를 저장한다.
• bracketCount는 [를 만났을 때 증가하고 ]를 만나면 감소한다.
• for문을 통해 s를 탐색한다.
• 숫자를 만나면 count에 추가한다.
• bracketCount가 0일 때 [를 만나면 내부의 문자열을 다시 decodeString으로 풀기 위해 시작 지점을 bracketStart에 저장한다.
• brackCount가 0일 때만 같은 레벨이므로 result에 문자를 추가한다.
• brackCount가 ]를 만나고 0이 되면 괄호 내부 영역이 정해지므로 내부 문자열을 decodeString으로 풀고 count만큼 반복해 result에 추가한다.
• 모든 문자열을 다 탐색하면 result를 반환한다.

var decodeString = function(s) {
  let result = "";
  const nums = new Set(['0','1','2','3','4','5','6','7','8','9']);
  let count = 0;
  let bracketCount = 0;
  let bracketStart = 0;
  for (let i = 0 ; i < s.length; i++){
    if (s[i] === '[') {
      if (bracketCount === 0) bracketStart = i;
      bracketCount++;
    } else if (s[i] === ']') {
      bracketCount--;
      if (bracketCount === 0) {
        result += decodeString(s.slice(bracketStart + 1, i)).repeat(count);
        count = 0;
      }
    } else if (bracketCount === 0) {
      if (nums.has(s[i])) { 
        count = count * 10 + Number(s[i]);
      } else {
        result += s[i];
      }
    }
  }
  return result;
};

재귀를 통해 문제를 풀었기 때문에 공간은 괄호의 깊이만큼 사용하고, 시간은 level별 길이만큼 추가로 사용하므로 O(n)보다는 크다.

2. Stack

괄호가 열리고 닫힐 때를 기준으로 stack에 저장하고 괄호가 닫힐 때 앞의 repeat count만큼 현재 저장된 값을 반복해 추가한다면 stack과 괄호의 특성을 이용해 구현할 수 있다.

Algorithm

• s를 cur을 이용해 반복한다.
• cur이 숫자일 경우 count에 추가한다.
• cur이 [일 경우 앞에 있던 현재까지 저장한 tempStr과 count를 stack에 넣고 각각을 초기화한다.
• cur이 ]일 경우 stack에서 앞 문자열 front와 반복 횟수 repeatCount를 꺼낸다.
• 현재까지 저장한 tempStr을 반복 횟수 만큼 반복한 후 front와 합친다.
• 마지막으로 남은 tempStr이 결과가 된다.

var decodeString = function(s) {
  let result = "";
  const nums = new Set(['0','1','2','3','4','5','6','7','8','9']);
  let count = 0;
  let tempStr = "";
  const stack = [];
  for (let cur of s) {
    if (nums.has(cur)) {
      count = count * 10 + Number(cur);
    } else if (cur === '[') {
      stack.push([tempStr, count]);
      count = 0;
      tempStr = "";
    } else if (cur === ']') {
      const [front, repeatCount] = stack.pop();
      tempStr = front + tempStr.repeat(repeatCount);
    } else {
      tempStr += cur;
    }
  }
  return tempStr;
};

재귀와 스택 모두 레벨의 깊이만큼 공간을 사용한다. 하지만 재귀의 경우 다음 레벨 문자열의 끝을 알아야 재귀로 넘길 수 있기 때문에 괄호 안의 문자열의 길이 만큼 시간적으로 손해를 본다. 따라서 스택을 통해 구현하는 것이 시간 복잡도에서 이득을 볼 수 있다고 생각한다. 하지만 javascript에서 문자열은 방식이 원시값이기 때문에 매번 문자열을 더하는 방식이 상당한 시간, 공간적 손해를 일으킨다. 따라서 문자열 처리에 대부분의 시간이 소요되어 1번 알고리즘이 실제 성능이 좋게 나온것으로 생각된다.