LeetCode / Isomorphic Strings - オットセイの経営日誌

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

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

Two strings 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.

Example 1:
Input: s = "egg", t = "add"
Output: true

Example 2:
Input: s = "foo", t = "bar"
Output: false

Example 3:
Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s and t have the same length.

2つの同じ長さの文字列があって、文字iを文字jに置き換えると文字列sが文字列tに変わる、という対応関係が崩れていないことをisomorphicと言うそうです。

数学では同型写像を意味するそうです（聞いたこともない用語でしたが）。

解法がたくさんあって面白いですが、計算量オーダー的にはそこまで大きな差はありません。

解答・解説

解法1

sの各文字をkey, tの各文字をvalueに持つdictと、tの各文字をkey, sの各文字をvalueに持つdictの2つを用意し、対応関係をチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_d = {}; t_d = {}
        for i,j in zip(s,t):
            if i in s_d and s_d[i] != j:
                return False
            elif j in t_d and t_d[j] != i:
                return False
            else:
                s_d[i] = j
                t_d[j] = i
        return True

2つdictを用意するので、空間計算量は $O(2n)$ とあまり効率的ではありませんが、分かりやすい解法かと思います。

解法2

同じ2つのdictを使う手法としては以下もあります。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        d1, d2 = {}, {}
        for i, val in enumerate(s):
            d1[val] = d1.get(val, []) + [i]
        for i, val in enumerate(t):
            d2[val] = d2.get(val, []) + [i]
        return sorted(d1.values()) == sorted(d2.values())

ただ、最後のsortに時間がかかるので時間計算量の面で劣ります。

解法3

文字列に対するfindメソッドで、文字列中の各文字が初めて出てくるインデックスを返させ、2つの文字列について同じ値が返ってくるかチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return [s.find(i) for i in s] == [t.find(j) for j in t]

ただ $O(n)$ のfindメソッドをn回繰り返すことになるので、時間計算量の面で劣ります。

解法4

文字列sと文字列t中の文字を集合としたときの要素数と、文字列sとt中の文字のペアを集合としたときの要素数が同じかどうかをチェックするという解法もあります。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return len(set(zip(s, t))) == len(set(s)) == len(set(t))

これが時間計算量/空間計算量的にも、コードの短さ的にも最も優れているかと思います。

解法5

最後に、アスキーコードを利用する解法。

アスキーコードの要素数である256個の要素からなるリストを用意します。
文字列sの各文字xをアスキーコードiに変換し、リストのi番目に、xのsにおけるインデックス+1を値として格納します。
文字列sが"abc"なら、ord("a")が97なので、リストの97番目の要素に0+1=1を格納します。
インデックス+1とするのは、リストの各要素の初期値を0としているためです。
このインデックスが文字列sとtでずれていないかをチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        l1, l2 = [0 for _ in range(256)], [0 for _ in range(256)]
        for i in range(len(s)):
            if l1[ord(s[i])] != l2[ord(t[i])]:
                return False
            l1[ord(s[i])] = i+1
            l2[ord(t[i])] = i+1
        return True