Javaで文字列がサブシーケンスかを判定する方法と高速化の考察

問題

文字列 s が文字列 t のサブシーケンス（部分列）か判定したい。

サブシーケンスとは、文字の順序を保ったまま一部の文字を取り出してできる文字列。

シンプル実装（`indexOf` を使用）

class Solution {
    public boolean isSubsequence(String s, String t) {
        int tIndex = 0;
        for (char ch : s.toCharArray()) {
            tIndex = t.indexOf(ch, tIndex);
            if (tIndex == -1) return false;
            tIndex++;
        }
        return true;
    }
}

2分探索を使った場合、どうなるのかと思ったので下記にまとめてみました

二分探索

class Solution {
    public boolean isSubsequence(String s, String t) {
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            //map は Character -> List<Integer> のマップ
            //computeIfAbsent は その文字 ch に対応するリストを取得
            //もしまだなければ新しい ArrayList を作る
            //その取得したリストに .add(i) する
            map.computeIfAbsent(ch, k -> new ArrayList<>()).add(i);
        }

        int prevIndex = -1;
        for (char ch : s.toCharArray()) {
            if (!map.containsKey(ch)) return false;

            List<Integer> positions = map.get(ch);
            int left = 0, right = positions.size() - 1;
            int nextIndex = -1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (positions.get(mid) > prevIndex) {
                    nextIndex = positions.get(mid);
                    right = mid - 1; // 左側により小さい候補がないか確認
                } else {
                    left = mid + 1;
                }
            }

            if (nextIndex == -1) return false;
            //sがaceでtがabcdeの場合、-1→0→2→4の順でprevIndexが更新される
            prevIndex = nextIndex;
        }

        return true;
    }
}

まとめ

シンプル実装は短くて直感的

高速化は複数回判定する場合に意味を持つ

二分探索の使い方も理解しておくと汎用的に応用可能