Why my Java O(mn) Codes get TLE problem?


  • 0
    G

    The basic idea is to use two hashmaps. The first is to record the words in L, the second is to record all words has L[0].length() in a (i, i + L[0].length() * L.length) window of string S. And compare those two maps. I think the time complexity is S.length() * L.length.

         int len = S.length();
         int len_word = L[0].length();
         List<Integer> result = new ArrayList<Integer>();
         int i = 0;
         HashMap<String, Integer> words = new HashMap<String, Integer>();
         
         for(i = 0; i < L.length; i++)
            if(words.containsKey(L[i]))
                words.put(L[i],words.get(L[i]) + 1 );
            else words.put(L[i], 1);
         int flag = 1;
            
         for(i = 0; i + len_word * L.length <= len; i++)
         {
             if(words.containsKey(S.substring(i, i + len_word)))
             {
                 flag = 1;
                 HashMap<String, Integer> temp = new HashMap<String, Integer>();
                for(int j = 0; j < L.length; j++)
                {
                	String word = S.substring(i + j  * len_word, i + (j + 1) * len_word);
                	if(words.containsKey(word))
                	{
                	    if(temp.containsKey(word))
                             temp.put(word, temp.get(word) + 1);
                         else temp.put(word, 1); 
                	}
                    else 
                    {
                        flag = 0;
                        break;
                    }
                 }
                 if(flag == 1)
    	        if(temp.equals(words))
    	        	result.add(i);
    	            
            }
    
         }
         return result;

Log in to reply
 

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