1923. Sentence Similarity III

2026-03-02
leetcode
리트코드 1923번 풀이

문제

Sentence Similarity III

풀이

아이디어

두 문장이 비슷하려면, 앞에서부터 일치하는 단어의 수(prefix)와 뒤에서부터 일치하는 단어의 수(suffix)의 합이 짧은 문장의 단어 수 이상이어야 한다. 그래야 prefix와 suffix 사이에 다른 단어가 존재할 수 있기 때문이다.

처음에 두 문장을 단어 배열로 나누고, 앞에서부터 일치하는 단어의 수를 센다. 그 다음 뒤에서부터 일치하는 단어의 수를 센다. 마지막으로 두 개의 합이 짧은 문장의 단어 수 이상인지 확인한다.

투 포인터 방식을 생각해내는 것이 어렵진 않았는데, 처음에 느낌(?)을 잘못 잡았더니 한 단어로 이루어진 문장 처리가 좀 까다로워서 삽질을 좀 했었다. 처음엔 양쪽에서 동시에 포인터를 좁혀오는 방식으로 시도했었는데, 이렇게 되면 한 단어로 이루어진 문장의 경우에는 포인터를 정상적으로 움직이기 위한 조건을 걸기가 좀 까다로웠다. prefix와 suffix를 따로 세는 방식이 훨씬 직관적이고 깔끔한 것 같다.

코드

function areSentencesSimilar(sentence1: string, sentence2: string): boolean {
  const words1 = sentence1.split(' ');
  const words2 = sentence2.split(' ');
  const minLen = Math.min(words1.length, words2.length);

  let front = 0;
  while (front < minLen && words1[front] === words2[front]) front++;

  let back = 0;
  while (back < minLen - front && words1[words1.length - 1 - back] === words2[words2.length - 1 - back]) back++;

  return front + back >= minLen;
}

시간 / 공간 복잡도

  • 시간 복잡도: O(n) — n은 짧은 문장의 단어 수
  • 공간 복잡도: O(n) — 단어 배열