O(n) solution : still time limit exceeds?


  • 0
    N

    import java.util.;
    import java.lang.
    ;
    import java.io.*;

    public class Solution {

        public List<String> findRepeatedDnaSequences(String s) {
            
            HashMap<String, Integer> encodings = new HashMap<String, Integer>(); 
            encodings.put("A", 1);
            encodings.put("C", 2);
            encodings.put("G", 3);
            encodings.put("T", 4);
            
            
            
            HashMap duplicates = new HashMap<Integer, String>();
            
            List<String> solution = new ArrayList<String>();
            
            if (s.length() < 10) return solution;
            
            StringBuilder str = new StringBuilder(s.substring(0,10));
            
            int initialHash = 0;
            int power  = 10;
            
            int last_firstEncoding = encodings.get(""+s.charAt(0));
            for (int i = 0; i < 10; i++)
            {
                int encoding = 0;
                if (encodings.get((""+s.charAt(i))) != null)
                {
                    encoding = encodings.get(""+s.charAt(i));
                    
                }
                initialHash += encoding*Math.pow(2, power);
                power--;
            }
            duplicates.put(initialHash, s.substring(0, 10));
            
            str = str.deleteCharAt(0);
            for (int i = 10; i < s.length(); i++)
            {
                char currentChar = s.charAt(i);
            	initialHash -=last_firstEncoding*Math.pow(2, 10);
            	initialHash = 2*(initialHash + encodings.get((""+currentChar)));
            	
            	str = str.append(currentChar);
            	if (duplicates.get(initialHash) != null)
            	{
            		solution.add(0, (String)duplicates.get(initialHash));
        	}
    
            	else
            	{
            		duplicates.put(initialHash, str.toString());
            	}
            	last_firstEncoding = encodings.get((""+s.charAt(i-9)));
            	str = str.deleteCharAt(0);
            }
            
            return solution;
        }
    

    }


Log in to reply
 

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