Ac solution code


  • 0

    The basic idea is to check all 10-letter-longs strings, there're (n - 10) strings:

    0..9 1..10 2..11 ... n-10..n-1
    

    Then use HashSet or HashMap to output the repeated strings.

    Soution1. Two HashSet - O(n) runtime; O(2n)=O(n) space - Special thanks to StefanPochmann

        public List<String> findRepeatedDnaSequences(String s) {
        	Set seen = new HashSet<String>(), repeated = new HashSet<String>();    	
            for (int i = 10; i <= s.length(); i++) {
            	String cur = s.substring(i - 10, i);
            	if (!seen.add(cur)) 
            		repeated.add(cur);
            }
            return new LinkedList<String>(repeated);
        } 
    

    Solution2. One HashMap - O(n) runtime; O(2n)=O(n) space

        public List<String> findRepeatedDnaSequences2(String s) {
        	Map<String, Integer>map = new HashMap<String, Integer>();
            List<String>res = new LinkedList<String>();
            for (int i = 10; i <= s.length(); i++) {
            	String cur = s.substring(i - 10, i);
            	int count =  map.containsKey(cur) ? map.get(cur) : 0;        	
                map.put(cur, ++count);        	
                if (count == 2) res.add(cur);   
            }
            return res;
        }
    

Log in to reply
 

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