String Composition

出处

Given a newspaper and message as two strings, check if the message can be composed using letters in the newspaper.

Solution

在什么情况下newspaper中出现的字符能够组成message?

首先,message中用到的字符必须出现在newspaper中。其次,message中任意字符出现的次数一定少于其在newspaper中出现的次数。一旦需要统计一个元素集中元素出现的次数,我们就应该想到哈希表。键是字符,值是字符在newspaper中出现的次数。那么,如果message中用到的字符没有出现在哈希表中,则构成失败;如果 message用到了某个哈希表中出现的字符,那我们可以将值减少,表示“消耗”了一个字符。如果最终某个值变成了负值,那么message中该字符出现的次数多于其在newspaper中出现的次数,构成失败。

Complexity

假设message长度为m ,newspaper长度为n,我们的算法需要hash整条message和整个newspaper,故时间复杂度O(m+n)。假设字符集大小为c,则平均空间是O(c)

Code

boolean canCompose(String newspaper, String message){
    if (message == null) return true;
    if (newspaper == null) return false;
    
    HashMap<Character, Integer> alphabet = new HashMap<Character, Integer>();
    
    for (int i = 0; i < newspaper.length(); i++){
        if (alphabet.containsKey(newspaper.charAt(i)){
            alphabet.put(newspaper.charAt(i), alphabet.get(newspaper.charAt(i))+1);
        } else {
            alphabet.put(newspaper.charAt(i), 1);
        }
    }
    
    for (int i = 0; i < message.length(); i++){
        if (!alphabet.containsKey(message.charAt(i)){
            return false;
        } else {
            if (alphabet.get(message.charAt(i)) == 0){
                return false;
            } else {
                alphabet.put(message.charAt(i), alphabet.get(nespaper.charAt(i))-1);
            }
        }
    }
    return true;
}