java time O(n) space O(1) hashmap


  • 0
    X
    boolean canConstruct(String ransomNote, String magazine) {
        // Early check
        if (ransomNote.length() > magazine.length())
            return false;
        Map<Character, Integer> magazineLetterCounter = new HashMap<>();
        // Count letters in magazine
        for (int index = 0; index < magazine.length(); index++) {
            if (magazineLetterCounter.containsKey(magazine.charAt(index))) {
                int newCounts = magazineLetterCounter.get(magazine.charAt(index));
                magazineLetterCounter.put(magazine.charAt(index), ++newCounts);
            } else
                magazineLetterCounter.put(magazine.charAt(index), 1);
        }
        /*
         * Traverse ransom note
         * Find letter from ransom note in map(magazineLetterCounter), then reduce count of the letter
         * return false if counts less than 0
         * return false if no matched letter found in map
         */
        for (int index = 0; index < ransomNote.length(); index++) {
            if (magazineLetterCounter.containsKey(ransomNote.charAt(index))) {
                int newCounts = magazineLetterCounter.get(ransomNote.charAt(index));
                if (--newCounts >= 0)
                    magazineLetterCounter.put(ransomNote.charAt(index), newCounts);
                else
                    return false;
            } else
                return false;
        }
        return true;
    }
    

Log in to reply
 

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