用bit来存储信息

Repeated DNA Sequences

A C G T4个character能够用0，1，2，3这个四个数字表示，也就是00，01，01，和11，每个只占用了2位，DNA sequence是10个连续的character，也就是能用20位来表达。一个int能够包含32位，因此我们可以用int来表示DNA sequence。

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        if (s == null || s.length() < 10) {
            return result;
        }

        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);

        Set<Integer> dna = new HashSet<Integer>();
        for (int i = 9; i < s.length(); i++) {
            int k = 0, num = 0;
            for (int j = i - 9; j <= i; j++) {
                int n = map.get(s.charAt(j));
                num |= n << k;
                k += 2;
            }
            if (dna.contains(num)) {
                String str = s.substring(i - 9, i + 1);
                if (!result.contains(str)) {
                    result.add(str);
                }
            }
            dna.add(num);
        }
        return result;
    }
}

Maximum Product of Word Lengths

在题干里已经点名了word只包含lowercase letters，总共只有26个，因此我们同样可以用一个int数字来表示一个word。

public class Solution {
    public int maxProduct(String[] words) {
        if (words == null || words.length == 0) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int num = 0;
            for (char c: word.toCharArray()) {
                num |= 1 << (c - 'a');
            }
            map.put(i, num);
        }

        int result = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((map.get(i) & map.get(j)) == 0) {
                    result = Math.max(result, words[i].length() * words[j].length());
                } 
            }
        }
        return result;
    }
}