187. Repeated DNA Sequences重復的DNA子串序列

［抄題］：

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.

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"Output: ["AAAAACCCCC", "CCCCCAAAAA"]

?[暴力解法]：

時間分析：

空間分析：

?[優化后]：

時間分析：

空間分析：

［奇葩輸出條件］：

1. set轉成arraylist直接放到括號里就行了

［奇葩corner case］：

［思維問題］：

［英文數據結構或算法，為什么不用別的數據結構或算法］：

10個數，從開始算，加到9就可以了。

?

for (int i = 0; i + 9 < s.length(); i++)

?

.substring包左不包右，所以必須寫十位數。但是inde

String ten = s.substring(i, i + 10);

?

 
beginIndex =< str的值 < endIndex

?

［一句話思路］：

［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫圖］：

［一刷］：

1. set的判斷語句 沒加就自己自動加 沒必要再寫一遍
2. set用add，map用put

［二刷］：

［三刷］：

［四刷］：

［五刷］：

? [五分鐘肉眼debug的結果]：

［總結］：

set就是判重，一個不夠用可以用兩個

［復雜度］：Time complexity: O(n) Space complexity: O(n)

［算法思想：迭代/遞歸/分治/貪心］：

［關鍵模板化代碼］：

［其他解法］：

［Follow Up］：

［LC給出的題目變變變］：

?[代碼風格] ：

?[是否頭一次寫此類driver funcion的代碼] ：

?[潛臺詞] ：

?

class Solution {public List<String> findRepeatedDnaSequences(String s) { //ini: two setsList<String> result = new ArrayList<String>();Set<String> seen = new HashSet<String>();Set<String> ten = new HashSet<String>();//ccif (s.length() == 0) return result;//for loop: get substringfor (int i = 0; i + 9 < s.length(); i++) {String str = s.substring(i, i+ 10);if (!seen.add(str)) ten.add(str);}//returnreturn new ArrayList(ten);}
}

?