🖋

LeetCode 205. Isomorphic Strings

に公開
Go
LeetCode
tech

はじめに

LeetCode 「205. Isomorphic Strings」の問題をGoで解きました。

問題

https://leetcode.com/problems/isomorphic-strings/description

問題文

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

和訳
2つの文字列sとtが与えられたとき、それらが同型かどうかを判定せよ。

二つの文字列sとtは、sの文字を置き換えてtを得ることができれば同型である。

ある文字が出現する場合はすべて、文字の順序を保ったまま別の文字に置き換えなければならない。2つの文字が同じ文字に対応することはないが、1つの文字がそれ自身に対応することはある。

例

Input: s = "egg", t = "add"

Output: true

Explanation:

The strings s and t can be made identical by:

・Mapping 'e' to 'a'.
・Mapping 'g' to 'd'.

Input: s = "foo", t = "bar"

Output: false

Explanation:

The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.

Input: s = "paper", t = "title"

Output: true

制約

  • 1 <= s.length <= 5 * 104
  • t.length == s.length
  • s and t consist of any valid ascii character.

解答1

2つの文字列が同型か判定するの問題です。
順序を保ったまま文字を置き換えられてば同型と言えます。

まず、重複した文字に着目する方法を考えました。
文字が重複する場合、重複した文字の出現位置が一致すれば同型と判定できます。

コード

func isIsomorphic(s string, t string) bool {
  length := len(s)

  sIndexMap := make(map[byte]int)
  tIndexMap := make(map[byte]int)

  for i := range length {
    sCh := s[i]
    tCh := t[i]

    sValue, sExist := sIndexMap[sCh]
    tValue, tExist := tIndexMap[tCh]
    if sExist != tExist {
      return false
    }
    if sValue != tValue {
      return false
    }

    sIndexMap[sCh] = i
    tIndexMap[tCh] = i
  }

  return true
}

sIndexMap,tIndexMap は各文字の最後のindexを保存しています。
文字をキーとしたバリューの有無が一致しない、
あるいはindexの値が一致しない場合にfalseを返します。

計算量

  • 時間的計算量：O(n)
  • 空間的計算量：O(1)
    • 英字の文字数は定数であり、最大でも256文字なので定数空間とみなせる

解答2

解答1は文字の出現したindexを利用した解答でしたが、文字同士をマッピングという実装も可能です。
sの文字とtの文字の対応を記録する方法です。

コード

func isIsomorphic(s string, t string) bool {
  length := len(s)

  stMap := make(map[byte]byte)
  tsMap := make(map[byte]byte)

  for i := range length {
    sCh := s[i]
    tCh := t[i]

    stValue, stExist := stMap[sCh]
    tsValue, tsExist := tsMap[tCh]
    if stExist != tsExist {
      return false
    }
    if stExist && tsExist {
      if stValue != tCh || tsValue != sCh {
        return false
      }
    }

    stMap[sCh] = tCh
    tsMap[tCh] = sCh
  }

  return true
}

計算量

  • 時間的計算量：O(n)
  • 空間的計算量：O(1)

解答３

さらに効率的な実装として、スライスを使う方法もあります。
LeetCode上でも、こちらが最もハイパフォーマンスでした。

解答2と同じように、双方向でマッピングを行うものですが、
ASCII文字（最大128種類）を前提として、[]int（長さ128のスライス）を使って管理しています。

コード

func isIsomorphic(s string, t string) bool {
  length := len(s)

  sMap := make([]int, 128)
  tMap := make([]int, 128)

  for i := range length {
    sCh := s[i]
    tCh := t[i]

    if sMap[sCh] == 0 && tMap[tCh] == 0 {
      sMap[sCh] = int(tCh)
      tMap[tCh] = int(sCh)
    } else if sMap[sCh] != int(tCh) || tMap[tCh] != int(sCh) {
      return false
    }
  }

  return true
}

例えば、例1の場合は以下となります。

  1. i = 0
    • sCh = 'e' (101), tCh = 'a' (97)
    • map1['e'] == 0, map2['a'] == 0 → 対応づけ
    • map1[101] = 97, map2[97] = 101
  2. i = 1
    • sCh = 'g' (103), tCh = 'd' (100)
    • 両方未定義 → 対応づけ
  3. i = 2
    • 同じ文字 'g'、'd'
    • すでに map1['g'] == 'd'、map2['d'] == 'g' → OK

計算量

  • 時間的計算量：O(n)
  • 空間的計算量：O(1)

参考

今回の問題と似ている問題も以下の記事で紹介していますので、参考にしてください。

GitHubで編集を提案

Discussion