# Java solution using Rabin-Karp algorithm.

• Think the solution is a simple variant version of Rabin-Karp algrotihm.
(The code below isn't very efficient, but it can pass all the tests and the big idea is RK.)

``````import java.util.*;

public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
// Simple application of Rabin-Karp
Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();
ht.put('A', 0);
ht.put('C', 1);
ht.put('G', 2);
ht.put('T', 3);

List<String> result = new ArrayList<String>();
if (s.length() < 10)
return result;

// transform String to integer array
int[] a = new int[s.length()];
for (int i = 0; i < s.length(); i++)
a[i] = ht.get(s.charAt(i));

// transform into hashcode array
int val = 1;
int sum = a[0];
for (int i = 1; i <= 9; i++) {
sum = sum * 4 + a[i];
val = val * 4;
} // for

// hashcode array
int[] sarray = new int[a.length - 10 + 1];
sarray[0] = sum;
for (int i = 10; i < a.length; i++) {
int current = i - 10 + 1;
//sarray[i - 10 + 1] = sarray[i - 10]
sarray[current] = (sarray[current - 1] % val) * 4 + a[i];
}

// used as a counter
Hashtable<Integer, Integer> hm = new Hashtable<Integer, Integer>();
for (int i = 0; i< sarray.length; i++) {
if (!hm.containsKey(sarray[i]))
hm.put(sarray[i], i);
else {
int index = hm.get(sarray[i]);
if (index < 0) // already confirmed no need to check this guy anymore
continue;
// hash code match, and we need to further prove it by comparation
int k = 0;
for (; k < 10; k++) {
if (s.charAt(index + k) != s.charAt(i + k))
break;
}
// real match case add it to the result
if (k == 10) {
hm.put(sarray[i], -1);
}
}
} // for

return result;
}
}``````

• This post is deleted!

• Could you explain the idea a little bit?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.