Improved Solution: Shortcut on the Magazine not the RansomNote


  • 5

    As the magazine could be much longer than the RansomNote, shortcutting the loop on the magazine will result in much better running complexity.

    First build the HashMap for the RansomNote, then loop on the magazine, and return true as soon as you removed all the characters from the Map.

    This change resulted in improving the running time from ~80ms to ~20ms for my code.

    public boolean canConstruct(String ransomNote, String magazine) {
    	if(ransomNote.length()>magazine.length()) return false;
    	if(ransomNote.isEmpty() && magazine.isEmpty()) return true;
    	Map<Character,Integer> charsCount = new HashMap<>();
    	for(char c: ransomNote.toCharArray()) {
    		if(charsCount.containsKey(c)) {
    			charsCount.put(c, charsCount.get(c)+1);
    		} else {
    			charsCount.put(c, 1);
    		}
    	}
    	for(char c: magazine.toCharArray()) {
    		if(charsCount.containsKey(c)) {
    			int count = charsCount.get(c);
    			if(--count==0) charsCount.remove(c);
    			else charsCount.put(c, count);
    		}
    		if(charsCount.keySet().size()==0) {
    			return true;
    		}
    	}
    	return false;
    }
    

  • 0
    M

    @fabrizio3
    Nice practical observation! Here is a C++ version:

            bool canConstruct(string ransom, string magazine) {
                auto N = ransom.size();
                if (magazine.size() < N)
                    return false;
    
                int freqs[26] = {};
                for (auto ch : ransom) freqs[ch - 'a']++;
    
                auto used = freqs;
                auto found = 0;
    
                for (auto ch : magazine) {
                    if (!used[ch - 'a'])
                        continue;
    
                    if (freqs[ch - 'a']-- == 0)
                        break;
    
                    if (++found == N)
                        break;
                }
    
                return found == N;
            }
    

Log in to reply
 

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