For problem Anagrams, time limit is exceeding


  • 0
    A

    I wrote following code but time limit is exceeding. any suggestion

    public class Solution {
        public List<String> anagrams(String[] strs) {
             List<String> lst = new ArrayList<String>();
    		 if(strs.length==1) return lst;
    		 for(int i =0; i< strs.length ; i++){
    		    
    			 for(int j= i+1; j <strs.length;j++){
    			
    				 
    				 if(anagram1 (strs[i], strs[j])){
    				
    				     	if(!lst.contains(strs[i])) {
    						lst.add(strs[i]); 
    					    
    					 }
    					if(!lst.contains(strs[j])) {
    						lst.add(strs[j]);
    					}
    				 }
    			 }
    		 }
    	      return lst;  
    	    }
    	public static boolean anagram1(String s, String t) {
    		if (s.length() != t.length())
    			return false;
    		if (s.length() == 1 && t.length() == 1) {
    			if (s == t) {
    				return true;
    			} else
    				return false;
    		}
    		int[] letters = new int[256];
    		int num_of_unique_characters = 0;
    		int num_of_characters_compelted = 0;
    		char[] givenString = s.toCharArray();
    		int value = 0;
    		for (char c : givenString) {
    			if (letters[c] == 0) {
    				num_of_unique_characters++;
    				letters[c] = 1;
    			} else {
    				value = letters[c];
    				letters[c] = value++;
    			}
    		}
    		char[] strin_to_compare = t.toCharArray();
    		for (char c : strin_to_compare) {
    			if (letters[c] == 0) {
    				// System.out.print("here");
    				return false;
    			} else {
    				value = letters[c];
    				letters[c] = --value;
    			}
    			if (letters[c] == 0) {
    				num_of_characters_compelted++;
    			}
    		}
    		
    		if (num_of_characters_compelted == num_of_unique_characters)
    			return true;
    		return false;
    
    	}
            
        
    }

  • 0
    A

    finally i was able to find a solution for this issue. We will sort each word alphabetically and store it in a hashmap and look for similar words.

    public static List<String> anagrams(String[] strs) {
             List<String> lst = new LinkedList<String>();
             if(strs ==null ||strs.length ==0) return lst;
             Map<String,Integer> map = new HashMap<String,Integer>();
             for(int i=0; i< strs.length; i++){
                 char[] c = strs[i].toCharArray();
                 Arrays.sort(c);
                 String word = new String(c);
         		
                 if(map.containsKey(word)){
                     lst.add(strs[i]);
                     if(map.get(word) >=0){
                         lst.add(strs[map.get(word)]);
                         map.put(word, -1);
                     }
                 }else map.put(word,i);
             }
    		
    	      return lst;  
    	    }

Log in to reply
 

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