Could you help me with my Java code ?


  • 0
    N

    The following is the AC answer:

     List<String> list = new ArrayList<String>();
        		 HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        	        int  value = 0;
        	        for(int i=0;i<s.length();i++){
        	           // String tmp = s.substring(i,i+10);
        	            value = value<<3&0x3FFFFFFF | ( s.charAt(i)&7);
        	            map.put(value, (map.get(value)==null?0:map.get(value))+1);
        	            if(map.get(value)==2){
        	                list.add(s.substring(i-9,i+1));
        	            }
        	        }
        	        return list;
        	    }
    

    but ,when I tried this , It shows Memory limit exceed !, could please help me ?

     public List<String> findRepeatedDnaSequences(String s) {
            Set<String> list = new HashSet<String>();
            Set<Integer> set = new HashSet<Integer>();
            int  value = 0;
            for(int i=0;i<s.length()-10;i++){
                String tmp = s.substring(i,i+10);
                value = value<<3&0x3FFFFFF | ( s.charAt(i)&7 );
                int index = Integer.valueOf(value);
                if(!set.add(index)){
                    list.add(tmp);
                }
            }
            List<String> l = new ArrayList<String>();
            for(String str:list){
                l.add(str);
            }
            return l;
        }

  • 0
    C

    I think it's probably because you used multiple hashset, and a hashset is actually backedup by a hashMap instance, so you are using 2 HashMaps.. and storing Strings in hashmap also tend to be more expensive. I had similar issues so I used hashCode as key and backed up with the starting index of the first string.

    public List<String> findRepeatedDnaSequences(String s) {
        HashMap<Integer,Integer> mys=new HashMap<Integer,Integer>();
        List<String> result=new ArrayList<String>();
        if(s.length()<10) return result;
        int temp;
        for(int i=0; i<s.length()-9; i++){
            String str=new String(s.substring(i,i+10));
            temp=str.hashCode();
            if(mys.containsKey(temp)){
                if(mys.get(temp)!=-1){
                    String str2=s.substring(mys.get(temp), mys.get(temp)+10);
                    if(str2.equals(str)){
                    result.add(str);
                    mys.put(temp,-1);
                    }
                }
            }else{
                mys.put(temp,i);
            }
        }
        return result;
    }

Log in to reply
 

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