位运算：BitMap

0187. 重复的DNA序列 (opens new window)

题目

所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

解析

使用 hash 存储全部子串，key 为子串数据，value 为子串出现次数，最后将出现此处超过 1 的返回即可。

代码

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        if (s.length() <= 10) {
            return vector<string>();
        }

        vector<string> ans;
        unordered_map<string, int> record;
        for (int i = 0; i <= s.length() - 10; i++) {
            string cur = s.substr(i, 10);
            if (record[cur] == 1) {
                ans.push_back(cur);
            }
            record[cur]++;
        }
        return ans;
    }
};

func findRepeatedDnaSequences(s string) []string {
	if len(s) <= 10 {
		return []string{}
	}
	ans, record := make([]string, 0), make(map[string]int)
	for i := 0; i <= len(s)-10; i++ {
		cur := s[i : i+10]
		if record[cur] == 1 {
			ans = append(ans, cur)
		}
		record[cur]++
	}
	return ans
}

0318. 最大单词长度乘积 (opens new window)

题目

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

解析

将每一个单词转换为一串二进制数字，每一位代表某个字母是否出现过，之后两层循环进行与运算判断是否重合，找到最大长度乘积。

代码

class Solution {
public:
    int maxProduct(vector<string>& words) {
        vector<int> bitWords(words.size());

        for (int i = 0; i < words.size(); i++) {
            bitWords[i] = 0;
            for (int j = 0; j < words[i].length(); j++) {
                bitWords[i] |= 1 << (words[i][j] - 'a');
            }
        }

        int ans = 0;
        for (int i = 0; i < words.size(); i++) {
            for (int j = i; j < words.size(); j++) {
                int product = words[i].length() * words[j].length();
                if ((bitWords[i] & bitWords[j]) == 0) {
                    ans = max(product, ans);
                }
            }
        }
        return ans;
    }
};

func maxProduct(words []string) int {
	bitWords := make([]int, len(words))
	for i := 0; i < len(words); i++ {
		for j := 0; j < len(words[i]); j++ {
			bitWords[i] |= 1 << (words[i][j] - 'a')
		}
	}
	ans := 0
	for i := 0; i < len(words); i++ {
		for j := i; j < len(words); j++ {
			if bitWords[i]&bitWords[j] == 0 && len(words[i])*len(words[j]) > ans {
				ans = len(words[i]) * len(words[j])
			}
		}
	}
	return ans
}