【競技プログラミング】「Isomorphic Strings」with Python | LeetCode #205

こちらは「Isomorphic Strings」のPythonによる解答例となっております。この問題は、2つの文字列が同型であるかどうかを判定する問題です。

問題

2つの文字列 s と t が与えられたとき、s の文字を t の文字に 1 対 1 で対応させることができる場合、s と t は同型であるといいます。例えば、egg と add は同型ですが、foo と bar は同型ではありません。

s と t の長さは同じです。
1 <= s.length <= 5 * 10^4
s と t は英文字のみで構成されています。

解法

この問題は、文字列を1文字ずつ比較し、1対1で対応付けるアルゴリズムを用いることができます。

アルゴリズムの概要を以下に述べます。

空の辞書を用意します。
s の各文字と t の各文字を1文字ずつ比較します。
辞書に s の文字をキー、t の文字を値として追加します。
s の文字を辞書のキーとして検索し、対応する t の文字が t 中に存在しない場合、同型ではないと判定します。
t の文字を辞書の値として検索し、対応する s の文字が s 中に存在しない場合、同型ではないと判定します。

Pythonコード

以下のコードが、「Isomorphic Strings」を解くためのPythonプログラムとなります。

### Function ##################################################################

def solve(num=0):
    
    solver  = Solution().isIsomorphic
    
    if 1 <= num <= Input().input: id_LIST = [num]
    else: id_LIST = [id+1 for id in range(Input().input)]
    
    for id in id_LIST:
        data    = Input(id)
        ans     = solver(data.s, data.t)
        result  = "OK" if ans==data.ans else "NG"
        print(f"[{str(id).zfill(3)}] {result}")

### Class #####################################################################

class Solution(object):
    
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return len(set(zip(s, t))) == len(set(s)) == len(set(t))

#==============================================================================

class Input:
    
    def __init__(self, num=0):
        
        if num == 1:
            self.s = "egg"
            self.t = "add"
            self.ans    = True
        
        elif num == 2:
            self.s = "foo"
            self.t = "bar"
            self.ans    = False

        elif num == 3:
            self.s = "paper"
            self.t = "title"
            self.ans    = True
        
        else:
            self.input  = 3

### Main ######################################################################

if __name__ == "__main__":

    solve()

###############################################################################