재귀적으로 JavaScript에서 문자열의 모든 부분 문자열 구하기

문자열 하나를 유일한 인수로 받아, 해당 문자열에서 만들 수 있는 모든 부분 문자열(substring)을 재귀적으로 생성한 뒤 배열로 반환하는 JavaScript 함수를 작성해 보겠습니다.

길이가 n인 문자열은 시작 위치와 끝 위치의 조합에 따라 총 n × (n + 1) / 2개의 부분 문자열을 가집니다. 예를 들어 'example'(7자)의 경우 28개의 부분 문자열이 만들어집니다.

반복문으로 살펴보는 기본 아이디어

시작 인덱스 i와 끝 인덱스 j를 이중 반복문으로 조합하면 모든 부분 문자열을 손쉽게 추출할 수 있습니다. String.prototype.slice() 메서드로 각 구간의 문자열을 잘라 배열에 담는 방식입니다.

const str = 'example';

const buildSubstrings = (str = '') => {
  let i, j;
  const res = [];
  for (i = 0; i < str.length; i++) {
    for (j = i + 1; j < str.length + 1; j++) {
      res.push(str.slice(i, j));
    }
  }
  return res;
};

console.log(buildSubstrings(str));

출력 결과

콘솔에는 다음과 같이 출력됩니다.

[
  'e', 'ex', 'exa',
  'exam', 'examp', 'exampl',
  'example', 'x', 'xa',
  'xam', 'xamp', 'xampl',
  'xample', 'a', 'am',
  'amp', 'ampl', 'ample',
  'm', 'mp', 'mpl', 'mple',
  'p', 'pl', 'ple',
  'l', 'le', 'e'
]

재귀(recursion)로 구현하기

재귀를 활용하려면 문제를 더 작은 단위로 나누면 됩니다. 즉, 현재 문자열의 첫 번째 문자로 시작하는 모든 부분 문자열을 먼저 만들고, 첫 문자를 제외한 나머지 문자열에 대해 같은 작업을 반복하는 방식입니다.

const buildSubstringsRecursively = (str = '') => {
  // 종료 조건(base case): 남은 문자가 없으면 빈 배열 반환
  if (!str.length) return [];

  // 첫 번째 문자로 시작하는 부분 문자열들
  const headSubstrings = [];
  for (let len = 1; len <= str.length; len++) {
    headSubstrings.push(str.slice(0, len));
  }

  // 나머지 문자열에 대해 재귀 호출
  return [...headSubstrings, ...buildSubstringsRecursively(str.slice(1))];
};

console.log(buildSubstringsRecursively('example'));

이 함수는 문자열이 빈 값이 될 때까지 자기 자신을 호출하며, 매 단계마다 현재 문자열의 접두사(prefix)들을 결과 배열에 추가합니다. 실행 결과는 앞서 본 반복문 버전과 완전히 동일합니다.

참고: 중복 제거

입력 문자열에 같은 문자가 반복되면 동일한 부분 문자열이 여러 번 포함될 수 있습니다. 중복 없이 고유한 부분 문자열만 필요하다면 결과를 Set으로 감싸주면 됩니다.

const uniqueSubstrings = [...new Set(buildSubstringsRecursively('banana'))];

정리

부분 문자열 생성은 이중 반복문으로도 충분히 해결되지만, 재귀로 표현하면 "첫 문자로 시작하는 경우 + 나머지에 대한 반복"이라는 문제의 구조가 코드에 그대로 드러난다는 장점이 있습니다. 길이가 n인 문자열의 부분 문자열 개수는 n(n + 1) / 2개이므로, 입력이 커질수록 결과 배열의 크기가 빠르게 늘어난다는 점도 기억해 두면 좋습니다.