同形文字列Leetcodeソリューション  


難易度 簡単に
よく聞かれる Adobe Amazon (アマゾン) Apple ブルームバーグ フェイスブック Googleポリシー インテル LinkedIn マイクロソフト オラクル Yahoo
アルゴリズム コー​​ディング ハッシュマップ 面接 インタビュー準備 リートコード LeetCodeSolutions 文字列

問題文  

この問題では、XNUMXつ与えられます ストリング、aおよびb。 私たちの目標は、XNUMXつの文字列が同型であるかどうかを判断することです。

XNUMXつの文字列は、最初の文字列の文字が、文字の相対的な順序を同じに保ちながら、その出現のすべてのポイントで任意の文字(それ自体を含む)に置き換えることができる場合にのみ、同形と呼ばれます。 XNUMX人のキャラクターが同じキャラクターにマップすることはできません。

s = "abb"  , t = "cdd"
true
s = "Google" , t = "123456"
false

同形文字列Leetcodeソリューションピン

アプローチ  

ハッシュマップを使用して、最初の文字列のすべての文字の置換を保存できます。 最初の文字の代わりがある位置に到達した場合、

  • 置換が他の文字列の文字と同じであるかどうかを確認できます。 そうでない場合、文字列を同形にすることはできません。
  • 最初の文字の置換がない場合は、XNUMX番目の文字が最初の文字列の他の文字の置換として使用されているかどうかを確認できます。 最初の文字列のすべての文字を一意の文字にマップする必要があるため、このチェックは重要です。 置換がXNUMX番目の文字である文字が存在しない場合、XNUMX番目の文字を最初の文字の置換として割り当てることができます。 それ以外の場合、文字列は同形ではありません。
参照
インターバルリートコードソリューションを挿入

アルゴリズム

  1. 初期化 文字 〜へ 文字 ハッシュマップ 置換 文字 〜へ ブール値 ハッシュマップ 中古
  2. 文字列内のすべての文字を繰り返します s 影響により t:
    • If 置換 含まれています s [i] キーとして:
      • If 置換[s [i]]!= t [i]
        • falseを返す
    • その他:
      • If used [t [i]] == true
        • falseを返す
      • セッションに 置換[s [i]] = t [i]
      • セッションに used [t [i]] = true
  3. trueを返す

同形文字列Leetcodeソリューションの実装

C ++プログラム

#include <bits/stdc++.h>

using namespace std;

bool isIsomorphic(string s , string t) {
    int n = s.length();

    unordered_map <char , char> replacement;
    unordered_map <char , bool> used;

    for(int i = 0 ; i < n ; i++)
    {
        if(replacement.count(s[i]))
        {
            if(replacement[s[i]] != t[i])
                return false;
        }
        else
        {
            if(used[t[i]])
                return false;
            replacement[s[i]] = t[i];
            used[t[i]] = true;
        }
    }

    return true;
}

int main() {
    string s = "abb" , t = "cdd";
    cout << (isIsomorphic(s , t) ? "true" : "false") << endl;
    return 0;
}

Javaプログラム

import java.util.*;

class isomorphic_string {
    public static void main(String args[]) {
        String s = "abb" , t = "cdd";
        System.out.println(isIsomorphic(s , t) ? "true" : "false");
    }

    public static boolean isIsomorphic(String s , String t) {
        HashMap <Character , Character> replacement = new HashMap <>();
        HashMap <Character , Boolean> used = new HashMap <>();

        for(int i = 0 ; i < s.length() ; i++) {
            if(replacement.containsKey(s.charAt(i))) {
                if(replacement.get(s.charAt(i)) != t.charAt(i))
                    return false;
            }
            else {
                if(used.containsKey(t.charAt(i)))
                    return false;
                replacement.put(s.charAt(i) , t.charAt(i));
                used.put(t.charAt(i) , true);
            }
        }

        return true;
    }
}
true

同形文字列の複雑さの分析Leetcodeソリューション

時間の複雑さ

O(N)、N =文字列sおよびtの長さ。

スペースの複雑さ 

O(1)、 入力には一定数の一意の文字が含まれるためです。

1