JavaScript로 부분 문자열 조합 여부 확인하기

두 개의 문자열을 각각 첫 번째와 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 문자열들을 각각 str1과 str2라고 부르겠습니다.

함수의 목표는 str1에서 일부 문자를 선택했을 때, 그 문자들의 순서를 유지하면서 str2를 만들어낼 수 있는지 확인하는 것입니다.

여기서 '부분 문자열 조합(substring combination)'이란 str1의 문자 중 일부를 건너뛸 수는 있지만, 선택된 문자들의 원래 순서는 반드시 지켜야 한다는 의미입니다. 이는 흔히 '부분 수열(subsequence)'이라고 불리는 개념과 같습니다.

예시

입력 문자열이 다음과 같다고 가정해 보겠습니다.

const str1 = 'desxooajmepwele';
const str2 = 'example';

이 경우 출력 결과는 다음과 같아야 합니다.

const output = true;

'example'은 str1에서 필요한 문자들을 순서대로 골라내어 만들 수 있기 때문입니다. 실제로 d-e-s-x-o-o-a-j-m-e-p-w-e-l-e 중에서 e, x, a, m, p, l, e에 해당하는 문자를 차례대로 선택하면 됩니다.

풀이 코드

가장 효율적인 접근 방식은 투 포인터(two pointer) 기법을 활용하는 것입니다. str2의 각 문자가 str1에서 이전에 찾은 위치 이후에 존재하는지 순차적으로 검사합니다.

const str1 = 'desxooajmepwele';
const str2 = 'example';

const containsString = (str1 = '', str2 = '') => {
   let [foundAt, next] = [0, 0];
   for(const char of str2){
      next = str1.slice(foundAt).indexOf(char);
      if (next === -1){
         return false;
      };
      foundAt += next + 1;
   };
   return true;
};

console.log(containsString(str1, str2));

코드 동작 원리

foundAt 변수는 str1에서 마지막으로 매칭된 문자의 다음 위치를 추적합니다. str2의 각 문자에 대해 slice(foundAt)으로 잘라낸 나머지 문자열에서 해당 문자를 찾고, 찾지 못하면(-1) 즉시 false를 반환합니다. 모든 문자를 성공적으로 찾으면 true를 반환합니다.

이 방식의 시간 복잡도는 O(n × m)이며, 여기서 n은 str1의 길이, m은 str2의 길이입니다. 실무에서는 slice 호출로 인한 추가 비용을 줄이기 위해 인덱스를 직접 관리하는 방식으로 최적화할 수도 있습니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true