【Java】Isomorphic Strings問題をO(n²)からO(n)に高速化してみた（LeetCode #256)

問題概要
2つの文字列 s と t が与えられたとき、それらが同型（isomorphic）かどうかを判定してください。
文字列 s と t は、s の文字を置き換えることで t を得ることができる場合、同型であるといいます。
すべての出現する文字は、他の文字に置き換えられる必要がありますが、文字の順序は保持されなければなりません。2つの異なる文字が同じ文字に対応してはいけませんが、1つの文字が自分自身に対応することは可能です。

初期実装（HashMap + containsValue）

実行速度：9ms
時間計算量：O(n²)
空間計算量：O(n)

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> map = new HashMap<>();
        int index = 0;
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                if (map.get(c) != t.charAt(index)) {
                    return false;
                }
            } else {
                if (map.containsValue(t.charAt(index))) {
                    return false;
                }
                map.put(c, t.charAt(index));
            }
            index++;
        }
        return true;
    }
}

問題点

containsValue() が内部で全値走査 → O(n)
ループ内で毎回呼ぶ → O(n²)　
補足：ループ[O(n)] * containsValue[O(n)] = O(n²)

改善1：双方向Mapを使う（O(n)）

containsValue() を避け、
s → t と t → s の双方向対応を 2つのHashMap で管理する。

実行速度：17ms
時間計算量：O(n)
空間計算量：O(n)

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> map1 = new HashMap<>();
        HashMap<Character, Character> map2 = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char s1 = s.charAt(i);
            char t1 = t.charAt(i);

            if (map1.containsKey(s1)) {
                if (map1.get(s1) != t1) return false;
            } else {
                map1.put(s1, t1);
            }

            if (map2.containsKey(t1)) {
                if (map2.get(t1) != s1) return false;
            } else {
                map2.put(t1, s1);
            }
        }
        return true;
    }
}

HashMap の containsKey(), get(), put() はO(1)であるため、O(n)になる。

それでも遅い？（9ms → 17msの理由）

理論上O(n)でも、実行時間が悪化することがあります。
要因: HashMapを2つ使う
内容：ハッシュ計算・参照コストが倍増

改善2：配列（int[256]）を使ってさらに高速化！

配列を活用することでインデックスアクセスのみになり、固定長配列にもなる。
実行速度：5ms
時間計算量：O(n)
空間計算量：O(1)

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] map1 = new int[256];
        int[] map2 = new int[256];
   
        for (int i = 0; i < s.length(); i++) {
            char s1 = s.charAt(i);
            char t1 = t.charAt(i);

            if (map1[s1] == 0 && map2[t1] == 0) {
                map1[s1] = t1;
                map2[t1] = s1;
            } else if (map1[s1] != t1) {
                return false;
            }
        }
        return true;
    }
}

まとめ

観点	改善前	改善後
データ構造	HashMap	配列
計算量	O(n²)	O(n)
実行時間	数十ms	数ms
可読性	普通	シンプルで明快

執筆者

Javaエンジニア。Hyrox挑戦中。
→ Qiita: @Katsu8998
https://hyrox-dashboard-kahbkakpyuagzybbm6buiz.streamlit.app/