java - 谁能帮我检查为什么我的解决方案会收到重复的结果？

Question

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:["AAAAACCCCC", "CCCCCAAAAA"].

我的代码:

public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
    List<String> res = new ArrayList<String>();
    
    if(s == null || s.length() == 0){
        return res;
    }
    
    for(int i = 0; i < s.length() - 10; i++){
        // System.out.print(occurance(s,sub) + ",");
        String sub = s.substring(i, i+10);//endIndex is exclusive
        System.out.print(occurance(s,sub) + ",");
        if(occurance(s,sub) > 1){
            res.add(sub);
        }
    }
    return res;
}

private int occurance(String s, String sub){
    int occurTimes = 0;
    for(int i = 0; i < s.length() - sub.length(); i++){
        for(int j = 0; j < sub.length(); j++){
            if(sub.charAt(j) != s.charAt(i+j)){
                break;
            }
            if(j == sub.length() - 1){
                occurTimes++; 
            }
        }
    }
    return occurTimes;
  }
}

Answer 1

好吧，findRepeatedDnaSequences 将为多次出现的子字符串调用 occurance(s,sub) 多次。

您可以通过将结果保存在 Set 而不是 List 中来解决这个问题。

public List<String> findRepeatedDnaSequences(String s) {
    Set<String> res = new HashSet<String>();

    if(s == null || s.length() == 0){
        return new ArrayList<String>();
    }

    for(int i = 0; i < s.length() - 10; i++){
        String sub = s.substring(i, i+10);
        System.out.print(occurance(s,sub) + ",");
        if(!res.contains(sub) && occurance(s,sub) > 1){
            res.add(sub);
        }
    }
    return new ArrayList<String>(res);
}

当然，你可以摆脱 occurance(s,sub) 并使你的代码更高效:

public List<String> findRepeatedDnaSequences(String s) {
    Set<String> dup = new HashSet<String>();
    Set<String> res = new HashSet<String>();

    if(s == null || s.length() == 0){
        return new ArrayList<String>();
    }

    for(int i = 0; i < s.length() - 10; i++){
        String sub = s.substring(i, i+10);
        if(!dup.add(sub)) { 
            res.add(sub); // add sub to res only if it is already present in dup
        }
    }
    return new ArrayList<String>(res);
}

输出(对于给定的输入):

[AAAAACCCCC, CCCCCAAAAA]