Java solution using Rabin-Karp algorithm.


  • 1
    C

    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) {
                        result.add(s.substring(i, i + 10));
                        hm.put(sarray[i], -1);
                    }
                }
            } // for
            
            return result;
        }
    }

  • 0
    K
    This post is deleted!

  • 0
    W

    Could you explain the idea a little bit?


Log in to reply
 

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