Repeated DNA sequence [hash determination repetition + sliding window + bit operation of binary coding]

Preface

When determining the repeated numbers in the array , You can use hash Record ; Turn an array into a string , When determining whether the string is repeated , can hash Record the string in the sliding window ; But string hashcode To get, you need to scan the string , and Character/Integer Is to directly obtain the original value as hashcode（hashcode After interference, act as hash value .）, So when string characters are binary encoded , Let the string map to a number , Get... Quickly hashcode.

One 、“ repeat ” Of DNA Sequence

Two 、hash Matching repetition + Binary code

1、hash Look for repetition

public List<String> findRepeatedDnaSequences(String s) {
    
        int n = s.length();

        Set<String> pool = new HashSet<>();
        Set<String> ans = new HashSet<>();

        for(int i = 0;i < n - 9;i++){
    
            String str = s.substring(i,i + 10);
            if(pool.contains(str) && !ans.contains(str)) ans.add(str);

            pool.add(str);
        }
        return new ArrayList<>(ans);
    }

2、 Bit operation practice of binary code

package everyday.bitManipulation;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//  Repetitive DNA Sequence .
public class FindRepeatedDnaSequences {
    
    /*  Because of the hashcode You need to scan the entire string , So you can encode a few strings , Just for 10 Encoding of substring . */
    public List<String> findRepeatedDnaSequences(String s) {
    
        int n = s.length();
        List<String> ans = new ArrayList<>();

        if (n <= L) return ans;
        //  Before initialization 9 Number .
        int x = 0, i = 0;
        while (i < L - 1) x = x << 2 | fx.get(s.charAt(i++));
        //  Start using the sliding window to get the substring integer Encoding as hash Of key
        Map<Integer, Integer> cnt = new HashMap<>();
        while (i < n) {
    
            x = (x << 2 | fx.get(s.charAt(i))) & (1 << L * 2) - 1;

            cnt.put(x, cnt.getOrDefault(x, 0) + 1);

            if (cnt.get(x) == 2) ans.add(s.substring(i - L + 1, i + 1));

            ++i;
        }
        return ans;
    }

    final static int L = 10;
    static Map<Character, Integer> fx = new HashMap<>();

    static {
    
        fx.put('A', 0);
        fx.put('C', 1);
        fx.put('G', 2);
        fx.put('T', 3);
    }
}

summary

1） Binary encoding can be more than string encoding , It is also common in subset scenarios , Binary mapping to subset ; Binary can also put 0/1 hash Dimension reduction , For example, a value can replace 31 position 0-1hash, deal with 26 Letters are more than enough .
2） Binary system / Bit operations are important , Practice more , It is helpful for many problem optimization .
3） A string of hashcode Acquisition is not O(1), It is O(n), character / The whole number is O(1).

reference

[1] LeetCode 187. Repetitive DNA Sequence