[LeetCode] 809. Expressive Words

문제

문자열 s와 단어 배열 words가 주어진다. 단어의 어떤 그룹(같은 문자가 연속된 덩어리)에 문자를 더 추가해서 그룹 길이를 3 이상으로 만드는 연산을 몇 번이든 적용해 s와 같아질 수 있으면 그 단어는 stretchy 하다. stretchy한 단어의 개수를 반환하라.

s = "heeellooo", words = ["hello", "hi", "helo"] → 1

hello → e를 3개로, o를 3개로 늘려 heeellooo. helo는 l이 1개라 ll(2개)을 만들 수 없어서 실패.

접근

문자를 하나씩 비교하는 대신 런렝스 인코딩으로 압축한다.

"heeellooo" → [["h",1], ["e",3], ["l",2], ["o",3]]
"hello"     → [["h",1], ["e",1], ["l",2], ["o",1]]

이렇게 두면 판정 조건이 그룹 단위로 단순해진다.

1. 그룹 개수가 다르면 탈락 (문자 순서가 다르다는 뜻)
2. 각 그룹에서 문자가 다르면 탈락
3. freqS < freqW면 탈락 — 늘리기만 가능하고 줄일 수는 없다
4. freqS > freqW인데 freqS < 3이면 탈락 — 확장 후 길이가 3 미만이면 연산 자체가 불가능

3번과 4번이 핵심이다. ll → lll은 되지만 l → ll은 안 된다. 최종 그룹 크기가 3 이상이어야 한다는 제약 때문.

코드

function expressiveWords(s: string, words: string[]): number {
  let stretchable = 0;

  const group = (str: string) => {
    const freq: [string, number][] = [];
    for (const char of str) {
      const last = (freq.at(-1) ?? [])[0];
      if (char !== last) {
        freq.push([char, 1]);
      } else {
        freq[freq.length - 1][1]++;
      }
    }
    return freq;
  };

  const groupS = group(s);

  for (const word of words) {
    const groupWord = group(word);
    if (groupS.length !== groupWord.length) {
      continue;
    }

    let matched = true;
    for (let i = 0; i < groupWord.length; i++) {
      const [strS, freqS] = groupS[i];
      const [strW, freqW] = groupWord[i];
      const unStretchable = freqS > freqW && freqS < 3;
      if (strS !== strW || freqS < freqW || unStretchable) {
        matched = false;
        break;
      }
    }

    if (matched) {
      stretchable++;
    }
  }

  return stretchable;
}

복잡도

• 시간: O(|s| + Σ|words[i]|) — 각 문자열을 한 번씩만 훑는다
• 공간: O(|s| + max|words[i]|) — 그룹 배열

groupS를 루프 밖에서 한 번만 계산하는 게 포인트. 단어마다 s를 다시 압축하면 불필요한 O(n·m)이 된다.

실수하기 쉬운 지점

freqS !== freqW && freqS < 3 으로 쓰면 틀린다. freqS < freqW(줄어드는 경우)는 3 이상이든 미만이든 무조건 불가능하므로 별도로 걸러야 한다. 두 조건을 하나로 합치려다 freqS = 5, freqW = 7 같은 케이스를 통과시키는 실수가 나온다.