Accepted Solution In Java (60ms)


  • 0
    M

    The solution is to first create a dictionary with key as each letter from magazine and value as the count of its occurrence. Then for each character in ransome note check if the corresponding character is available in the dictionary and reduce the count by 1. If at any time while checking the above either the dictionary doesn't have the letter or the count is 0, then we cannot form the ransome note from the magazine.

    We can do the same by first constructing map from ransome note and then going through magazine characters. Below solution is implementation of the first logic.

    		 Map<Character,Integer> map = new HashMap<Character,Integer>();
    		 if(magazine == null || ransomNote == null){
    			 return false;
    		 }
                   ///Creating dictionary
    		 for(Character c: magazine.toCharArray()){
    			if(map.containsKey(c)){
    				map.put(c, map.get(c)+1);
    			}
    			else{
    				map.put(c, 1);
    			}
    		 }
                     ///Checking letters from ransome note in magazine
    		 for(Character c: ransomNote.toCharArray()){
    			 if(map.containsKey(c) && map.get(c)>0){
    				 map.put(c, map.get(c)-1);
    			 }
    			 else{
    				 return false;
    			 }
    		 }
    		 return true;
    	 }
    

    Time complexity is O(m+n) where m and n are length of each input strings


Log in to reply
 

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