# LeetCode Easy 205. Isomorphic Strings

tags: leetcode

問題

• Explore
• Problems

アイデア

文字列sとtが与えられた時に，isomorphicかどうか調べろという問題です．

isomorphicとはsの文字がtの文字へ一対一に写像出来るということです．

ただし，2種類の文字が同じ文字に写像されることはなく，ある文字がその文字自身に写像されることはないです．

文字列の長さが同じという条件でこの問題を解く必要が有ります．

写像なので連想配列を使えば良いです．

解法

• まずはsの文字をkeyとし，tの文字をvalueとする連想配列を使います．
  • s[i]をkeyとしてないならば，新しく追加します．
  • あるならば，それが今までのvalueと同じか確認します．
    • 違う場合はfalseを返します．
• 次に，2種類の文字が同じ文字に写像されていないかを確認します．そのためにtからsへの連想配列を使います．
  • t[i]をkeyとしてないならば，s[i]をvalueとするものを新しく追加します．
  • あるならば，それが今までのvalueと同じか確認します．
    • 違う場合はfalseを返します．
• 文字列全体でこれを行い，falseが出ていなければtrueを返します．

計算量

s, tの文字列の大きさをそれぞれN, Mとします．

• 時間計算量
  • 文字列を走査するので$O(N + M)$です
• 空間計算量
  • 多くてもアルファベットの数の2倍にしかならないので$O(1)$

C++

class Solution {
public:
  bool isIsomorphic(string s, string t) {
    unordered_map<char, char> s2t, t2s;
    for (auto i  = 0; i < s.size(); ++i) {
      if (s2t.find(s[i]) == s2t.end())
        s2t[s[i]] = t[i];
      else if (s2t[s[i]] != t[i])
          return false;
      
      if (t2s.find(t[i]) == t2s.end())
        t2s[t[i]] = s[i];
      else if (t2s[t[i]] != s[i])
          return false;
    }
    return true;
  }
};