Zenn
🐷

LeetCoding Challenge Oct. 17: Repeated DNA Sequences

2020/10/17に公開
Java
LeetCode
tech

LeetCode October Challenge の 17 日目。

今日の問題は Repeated DNA Sequences。

問題の概要

  • 与えられた文字列 (DNA シーケンス) において 2 回以上出現する長さ 10 文字のシーケンスを列挙する

考え方

  • DNA シーケンスというか文字列の重複検出に使えるアルゴリズムを挙げてみよう
    • この手の問題の定石とも言える接尾辞配列 (suffix array) を利用する方法がすぐに思いつきますね
      • 接尾辞配列から LCP を求めれば、10 文字以上の重複は容易に検出できるはず
    • トライ木 (trie) を使う方法もありえますね
      • 長さ 10 文字の部分文字列を順次トライ木に登録していきつつ、重複を検出する
    • あとは ラビン-カープ の文字列探索アルゴリズムも使えそう
  • 今回はこれらの方法とは異なるアプローチで解いてみることにしよう 💪
  • 考え方は以下の通り
    • 文字列で使われているアルファベットは A, C, G, T の 4 つ
      • これらはそれぞれ 2 ビットで表現できるね
    • 重複検出したいシーケンスの長さは 10 文字だから、このシーケンス全体を 20 ビットで表現できちゃう 🥰
      • 32 ビット整数すなわち int で表現できるね 👍
    • この部分文字列を表す 20 ビットの数値を インデックス と見立てて、大きさ 2^{20} ビット (すなわち 128KB) の 2 つのビットフラグテーブルを管理するよ
      • 1 つ目のビットフラグテーブルは、インデックスに該当するシーケンスが過去に 1 度以上出現したかどうかを表現する
      • 2 つ目のビットフラグテーブルでは、同様にインデックスに該当するシーケンスが重複するシーケンスとしてすでに出力されたかどうかを表現する
  • とてもシンプルなアルゴリズムなのでサクッと実装 → submit → 一発 accept 🤗
    • Runtime: 5 ms で Your runtime beats 98.74 % of java submissions. はまずまずの結果かな？
    • 分布を見るとこんな感じ 分布
      • Runtime 4ms 以下の submit を見てみると、アルゴリズムは同じっぽい

コード

class Solution {
    static final byte[] TABLE;

    static {
        TABLE = new byte[256];
        TABLE['C'] = 1;
        TABLE['G'] = 2;
        TABLE['T'] = 3;
    }

    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() <= 10) {
            return Collections.emptyList();
        }

        int sequence = 0;
        for (int i = 0; i < 9; i++) {
            sequence = (sequence << 2) | TABLE[s.charAt(i)];
        }

        List<String> result = new ArrayList<>(s.length());

        BitSet bits = new BitSet(2 * (1 << 20));
        for (int i = 9; i < s.length(); i++) {
            sequence = ((sequence << 2) | TABLE[s.charAt(i)]) & 0x000f_ffff;

            int index = sequence * 2;
            if (!bits.get(index)) {
                bits.set(index);
            } else {
                if (!bits.get(index + 1)) {
                    result.add(s.substring(i - 9, i + 1));
                    bits.set(index + 1);
                }
            }
        }

        return result;
    }
}

Discussion