java - 有人可以帮助我检查为什么我的解决方案收到重复的结果吗？

所有DNA由一系列缩写为A，C，G和T的核苷酸组成，例如：“ ACGAATTCCG”。在研究DNA时，有时识别DNA中的重复序列很有用。
  
  编写一个函数以查找在DNA分子中多次出现的所有10个字母长的序列（子串）。
  
  例如，
  
  给定s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"，
  
  返回：
  ["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;
  }
}

最佳答案

好吧，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]

关于java - 有人可以帮助我检查为什么我的解决方案收到重复的结果吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40990025/