My java solution(did not use bit operation)


  • 0
    Y

    Maybe it is not very efficient, use two hashsets, one is to hold the strings appearing once, and anther is to hold strings which show more than once. delete the string from the first one if it already appear more than once

    public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> map=new HashSet<String>();
        HashSet<String> set=new HashSet<String>();
        for(int i=0;i<s.length()-9;i++){
            String temp=s.substring(i,i+10);
            if(!set.contains(temp)){
                if(map.contains(temp)){
                    set.add(temp);
                    map.remove(temp);
                }
                else{
                    map.add(temp);
                }
            }
        }
        return new ArrayList<String>(set);
    }
    

    }


  • 0
    Y

    Sorry, guys, this does not work any more, seems now the problem has more strict memory limit.


  • 0
    A

    I am a newbie to leetcode. I tried this problem and did something similar in C# . I used a C# Dictionary (equivalent to Hashmap in Java) which uses a key value pair. First we enter a string : 1 pair and then when we get a repeat, we change the value to 2. Once the value is changed to 2, I ignore it if I get another repeat. That way we do not repeat strings. The advantage is it only needs one dictionary.


  • 0
    D

    You can use value boolean too. Using integer need more memory ^_^


  • 3
    D

    You can use only 1 hashmap. And btw, your solution is now not working, coz the memory limit will be raised now. Instead, you should try this code:

    public List<String> findRepeatedDnaSequences(String s) {
            List<String> list = new LinkedList<String>();
            HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
            for(int i = 0; i<s.length()-9; i++){
                int v = getV(s, i);
                if(!map.containsKey(v))
                    map.put(v, false);
                else{
                    if(map.get(v) == false){
                        list.add(s.substring(i, i+10));
                        map.put(v, true);
                    }  
                }
            }
            return list;
        }
        private int getV(String s, int index){
            int v = 0;
            for(int i = index; i<index+10; i++){
                int vv = 0;
                if(s.charAt(i) == 'A') vv = 0;
                else if(s.charAt(i) == 'C') vv = 1;
                else if(s.charAt(i) == 'G') vv = 2;
                else vv = 3;
                v <<= 2;
                v |= vv;
            }
            return v;
        }

Log in to reply
 

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