205. Isomorphic Strings

리트코드 205번 풀이

문제

Isomorphic Strings

풀이 1

아이디어

s→t 매핑을 Map으로, t에서 이미 사용된 문자를 Set으로 관리한다. 매핑된 문자로 s를 변환한 뒤 t와 비교해서 isomorphic인지를 확인한다.

코드

function isIsomorphic(s: string, t: string): boolean {
  const map = new Map();
  const set = new Set();
  const sArray = Array.from(s);

  for (let idx = 0; idx < s.length; idx++) {
    const c = s[idx];
    if (map.has(c)) sArray[idx] = map.get(c);
    else {
      if (set.has(t[idx])) return false;
      sArray[idx] = t[idx];
      map.set(c, t[idx]);
      set.add(t[idx]);
    }
  }

  return t === sArray.join('');
}

시간 / 공간 복잡도

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

풀이 2

아이디어

풀이 1과 동일한 방식인데 set 대신 map을 두번 사용하는 방법도 있다. s→t, t→s 양방향 Map을 이용해서 매핑이 충돌하면 false를 반환한다.

코드

function isIsomorphic(s: string, t: string): boolean {
  const mapST = new Map(); // s -> t 문자 매핑용
  const mapTS = new Map(); // t -> s 문자 매핑용

  for (let idx = 0; idx < s.length; idx++) {
    const cS = s[idx];
    const cT = t[idx];
    if (mapST.has(cS) && mapST.get(cS) !== cT) return false; // s에서 cS가 이미 매핑되어 있는데, 그 매핑이 cT가 아니라면 false
    if (mapTS.has(cT) && mapTS.get(cT) !== cS) return false; // t에서 cT가 이미 매핑되어 있는데, 그 매핑이 cS가 아니라면 false
    mapST.set(cS, cT);
    mapTS.set(cT, cS);
  }

  return true; // 모든 문자에 대해서 매핑이 질 이루어졌다면 true
}

시간 / 공간 복잡도

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