データ構造とアルゴリズム: 同型文字列

[[441407]]

同型文字列

LeetCode の質問へのリンク: https://leetcode-cn.com/problems/isomorphic-strings

2 つの文字列 s と t が与えられた場合、それらが同型であるかどうかを判断します。

s 内の文字を何らかのマッピングで置き換えて t を取得できる場合、2 つの文字列は同型です。

文字の出現ごとに、文字の順序を変更せずに別の文字にマッピングする必要があります。異なる文字を同じ文字にマッピングすることはできません。同じ文字は同じ文字にのみマッピングできます。また、文字はそれ自身にマッピングできます。

例1:

入力: s = "egg"、t = "add"
出力: true

例2:

入力: s = "foo"、t = "bar"
出力: false

例3:

入力: s = "paper"、t = "title"
出力: true

ヒント: s と t は同じ長さであると仮定できます。

アイデア

文字列に小文字がすべて含まれているわけではないので、配列を使用することは適切ではありません。マッピングには map を使用します。

2つのマップを使用して、s[i]とt[j]、t[j]とs[i]間のマッピング関係を保存します。対応がないことが判明した場合は、すぐにfalseを返します。

C++ コードは次のとおりです。

クラスソリューション{
公共：
    bool isIsomorphic(文字列 s, 文字列 t) {
        unordered_map< char , char > map1;
        unordered_map< char , char > map2;
 ( int i = 0, j = 0; i < s.size ( ); i++, j++) {
            if (map1.find(s[i]) == map1.end ()) { // map1はs[i]からt[j]へのマッピングを保存します
                map1[s[i]] = t[j];
            }
            if (map2.find(t[j]) == map2.end ()) { // map2はt[j]からs[i]へのマッピングを保存します
                map2[t[j]] = s[i];
            }
            // マッピングが一致しない場合は、すぐにfalseを返します 
            もし (map1[s[i]] != t[j] || map2[t[j]] != s[i]) {
戻る 間違い;
            }
        }
戻る 真実;
    }
 };

その他の言語

ジャワ

クラスソリューション{
パブリックブール値 isIsomorphic(文字列 s, 文字列 t) {
        Map<文字,文字> map1 = new HashMap<>();
        Map<文字,文字> map2 = new HashMap<>();
 ( int i = 0, j = 0; i < s.length(); i++, j++) {
            map1.containsKey(s.charAt(i)) の場合 {
                map1.put(s.charAt(i), t.charAt(j)); // map1はs[i]からt[j]へのマッピングを保存します
            }
            map2.containsKey(t.charAt(j)) の場合 {
                map2.put(t.charAt(j), s.charAt(i)); // map2はt[j]からs[i]へのマッピングを保存します
            }
            // マップできないのでfalseを返す 
            (map1.get(s.charAt(i)) != t.charAt(j) || map2.get(t.charAt(j)) != s.charAt(i)) の場合 {
戻る 間違い;
            }
        }
戻る 真実;
    }
 }

パイソン

クラスソリューション:
    def isIsomorphic(self, s: str, t: str) -> bool:
        default_dict1 = デフォルト辞書(str)
        default_dict2 = defaultdict(str) 
 
        len(s) != len(t) の場合:戻り値 間違い  
 
 iが範囲(len(s))内にある場合:
            default_dict1[s[i]]でない場合:
                default_dict1[s[i]] = t[i] 
 
            default_dict2[t[i]]でない場合:
                default_dict2[t[i]] = s[i] 
 
            default_dict1[s[i]] != t[i]またはdefault_dict2[t[i]] != s[i] の場合:
戻る 間違い  
 
戻る 真実

行く

func isIsomorphic(s 文字列, t 文字列) bool {
 map1 := make(map[byte]byte)
 map2 := make(map[byte]byte)
 i := 範囲 s {
  _の場合、ok := map1[s[i]]; !ok {
   map1[s[i]] = t[i] // map1はs[i]からt[j]へのマッピングを格納します
  }
  _の場合、ok := map2[t[i]]; !ok {
   map2[t[i]] = s[i] // map2はt[i]からs[j]へのマッピングを格納します
  }
  // マップできないのでfalseを返す 
  もし (map1[s[i]] != t[i]) || (map2[t[i]] != s[i]) {
戻る 間違い 
  }
 }
戻る 真実 
 }

JavaScript

 var isIsomorphic =関数(s, t) {
    len = s.length;とします。
    if(len === 0)戻り値 真実;
    maps = new Map();
    mapt = new Map();
 (i = 0, j = 0; i < len; i++, j++)の場合{
        （！maps.has(s[i])）の場合{
            maps.set (s[i],t[j]); // mapsはs[i]からt[j]へのマッピングを保存します
        }
        （！mapt.has(t[j])）の場合{
            mapt.set (t[j],s[i]); // maptはt[j]からs[i]へのマッピングを保存します
        }
        // マップできないのでfalseを返す 
        if(maps.get(s[i]) !== t[j] || mapt.get(t[j]) !== s[i]){
戻る 間違い;
        }
    };
戻る 真実;
 };