LeetCode 187. 重复的DNA序列

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

• 例如，"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

方法：哈希表

题目要求是返回出现至少两次长度为 10 的字符串

我们可以用一个哈希表统计 s 出现次数至多为两次所有长度为 10 的子串

将其中出现两次字符串输出

Java中的Map提供了getOrDefault()方法，对不存在的键值提供默认值的方法。

getOrDefault(Object key, V defaultValue)
当Map集合中有这个key时，则使用这个key对应的value值，如果没有就使用默认值defaultValue

class Solution {
    
        
    public static final int L = 10;
 
    public List findRepeatedDnaSequences(String s) {
        List ans = new ArrayList();
        Map cnt = new HashMap();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            int tmp=cnt.getOrDefault(sub, 0);
            if (tmp<2)
            {
                cnt.put(sub, ++tmp);
                if (cnt.get(sub) == 2) 
                {
                    ans.add(sub);
                }
                
            
            }
        }
        return ans;
    }
}