290. Word Pattern

2026-03-21
leetcode
리트코드 290번 풀이

문제

Word Pattern

풀이

아이디어

205 - Isomorphic Strings 와 거의 동일한 문제이다.

pattern의 각 문자와 s의 각 단어가 1:1 매칭이 되는지 확인해야 한다. 단순히 한 방향 매핑만을 확인하면 ab / dog dog 같이 다른 패턴에 같은 단어가 매핑되는 것을 확인할 수 없다. 따라서 양방향으로 매핑을 확인해야 한다.

205번 문제의 풀이 1처럼 set을 이용해서 이전에 매핑했던 단어인지를 확인하는 방법도 있지만, 이번에는 양방향 map을 이용해서 bijection을 검증했다.

코드

function wordPattern(pattern: string, s: string): boolean {
  const pToW = new Map();
  const wToP = new Map();

  const words = s.split(' ');

  if (pattern.length !== words.length) return false;

  for (let idx = 0; idx < pattern.length; idx++) {
    const p = pattern[idx];
    const w = words[idx];

    if (pToW.has(p) && pToW.get(p) !== w) return false;
    if (wToP.has(w) && wToP.get(w) !== p) return false;

    pToW.set(p, w);
    wToP.set(w, p);
  }

  return true;
}

시간 / 공간 복잡도

  • 시간 복잡도: O(n)
  • 공간 복잡도: O(n)