题解 | #重复的DNA序列#

题意整理

• 给定一个由'A',‘C’,'G','T'字符组成的DNA序列。
• 找出序列中所有长度为10的重复子串，并且按原序列的顺序输出。

方法一（暴力循环）

1.解题思路

• 新建一个list容器，用于存储目标子串。
• 然后遍历所有可能的目标子串，如果未出现过，并且在后面的序列还会出现，则加入到list。
• 将list转化为字符串数组返回。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串一维数组
     */
    public String[] repeatedDNA (String DNA) {
        int n=DNA.length();
        //新建list，用于存储目标子串
        List<String> list=new ArrayList<>();
        //新建set，用于去重
        Set<String> set=new HashSet<>();
        for(int i=0;i<n-9;i++){
            //当前长度为10的子串
            String cur=DNA.substring(i,i+10);
            //如果未出现过，并且在后面的序列还会出现，则加入到list
            if(!set.contains(cur)&&DNA.substring(i+1).indexOf(cur)!=-1){
                list.add(cur);
                set.add(cur);
            }
        }
        //转化为字符串数组
        return list.toArray(new String[list.size()]);
    }
}

3.复杂度分析

• 时间复杂度：需要遍历所有可能目标子串，总共$n-9n-9$个，判断每个子串是否重复的indexOf函数的时间复杂度为$O(n)O(n)$，所以时间复杂度是$O(n^2)O(n^2)$。
• 空间复杂度：最坏情况下，需要额外大小为$(n-9)\mathrm{/}2(n-9)/2$的list和set空间，所以空间复杂度为$O(n)O(n)$。

方法二（哈希表+TreeMap）

1.解题思路

• 定义一个treeMap，key为目标子串的索引，value为目标子串。定义一个map，key为目标子串，value为目标子串的索引。
• 遍历所有可能的目标子串。如果之前没有出现，则加入到map，如果出现过，并且treeMap之前没有，则加入到treeMap。
• 最后将treeMap所有的value按顺序加入到res。treeMap能保证key有序，所以与原DNA序列顺序一致。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param DNA string字符串 1
     * @return string字符串一维数组
     */
    public String[] repeatedDNA (String DNA) {
        int n=DNA.length();
        //key为目标子串的索引，value为目标子串
        TreeMap<Integer,String> treeMap=new TreeMap<>();
        //key为目标子串，value为目标子串的索引
        Map<String,Integer> map=new HashMap<>();
        for(int i=0;i<n-9;i++){
            String cur=DNA.substring(i,i+10);
            //如果之前没有，则加入到map
            if(!map.containsKey(cur)){
                map.put(cur,i);
            }
            else{
                //如果重复，并且treeMap之前没有，则加入到treeMap
                if(!treeMap.containsKey(map.get(cur))){
                    treeMap.put(map.get(cur),cur);
                }
            }
        }
        
        String[] res=new String[treeMap.size()];
        int id=0;
        //将treeMap所有的value加入到res，treeMap能保证key有序，所以与原DNA序列顺序一致
        for(Integer key:treeMap.keySet()){
            res[id++]=treeMap.get(key);
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：只需一层循环，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：最坏情况下，需要额外大小为$(n-9)\mathrm{/}2(n-9)/2$的map和treeMap空间，所以空间复杂度为$O(n)O(n)$。