Java Solution with pruning


  • 0
    M

    We can use pruning as number of characters in magazine is usually higher than a ransom note.

    When we find all the words in ransom note, we can exit instead of going through the entire magazine.

        if(ransomNote == null || ransomNote.isEmpty()) 
            return true;
    
        if(magazine == null || magazine.isEmpty())
            return false;
            
        Map<Character, Integer> charCount = new HashMap();
        
        for(char c : ransomNote.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        for(char c : magazine.toCharArray()) {
            if(charCount.containsKey(c)) {
                int previousCnt = charCount.put(c, charCount.get(c) - 1);
                
                if(previousCnt - 1 == 0) {
                    charCount.remove(c);
                    
                    if(charCount.size() == 0) 
                        return true;
                }
            }
        }
        return false;
    

    '''


Log in to reply
 

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