Java O(n) Easy To Understand, Optimal Solution


  • 1
    B

    Explanation
    The idea to this problem is to first record the frequency of each distinct character in magazine in a dictionary, charMap.

    Then, we scan through ransomNote, while decrementing character counts in charMap. If the count for any character is null or equal to 0, then that tells us there is not enough of that particular character in magazine, so we return false.

    If we scan through the entirety of ransomNote, then that means we had enough characters in magazine, so we return true.

    Time Complexity
    The time complexity is O(n) where n is the number of characters in input magazine, since we scan through all characters in magazine when constructing charMap and we scan through at most n characters in ransomNote (more than n characters means magazine obviously does not contain enough characters).

    class Solution {
        public boolean canConstruct(String ransomNote, String magazine) {
            // Quick check to see if ransomNote is impossible to be constructed
            if (ransomNote.length() > magazine.length()) {
                return false;
            }
    
            // Maps character to its frequency
            Map<Character, Integer> charMap = new HashMap<>();
            
            // Record the characters counts in magazine
            for (int i = 0; i < magazine.length(); i++) {
                char c = magazine.charAt(i);
                Integer count = charMap.get(c);
                
                if (count == null) {
                    charMap.put(c, 1);
                } else {
                    charMap.put(c, count + 1);
                }
            }
            // Decrement the character counts in ransomNote from charMap
            for (int i = 0; i < ransomNote.length(); i++) {
                char c = ransomNote.charAt(i);
                Integer count = charMap.get(c);
                
                // If magazine does not contain char c or not enough of it,
                //    return false
                if (count == null || count <= 0) {
                    return false;
                } 
                // Otherwise, we decrement the count for char c
                else {
                    charMap.put(c, count - 1);
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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