#383. Ransom Note

題目描述

給你兩個字串ransomNote和magazine，回傳true如果ransomNote可以從magazine中的字元組成，反之則回傳false。

每一個magazine中的字母只能被ransomNote使用一次。

限制條件

1. 1 <= ransomNote.length, magazine.length <= 10^5
2. ransomNote和magazine都是由小寫字母組成。

解題思路

Character Counting

假設magazine中出現的字元為正值，ransomNote中出現的字元為負值，則magazine的字元可以組成ransomNote的話，magazine減去ransomNote的每個字元值會大於等於0。

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        //a = 97;
        var letters = new int[26];
        foreach(char i in magazine){
            int pos = i - 97;
            letters[pos]++;
        }
        foreach(char i in ransomNote){
            int pos = i - 97;
            letters[pos]--;
        }
        foreach(int i in letters){
            if(i<0) return false;
        }
        return true;
    }
}

複雜度分析：

• 時間複雜度：花費總時間為( m + n + 26 )，因此時間複雜度為O(m+n)。
• 空間複雜度：使用空間沒有增加，因此為O(1)。

Hash Table

同Character Counting的解題概念，只是換成使用Hash Table來儲存字元。

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Hashtable ht = new Hashtable();
        foreach(char i in magazine){
            if(ht.Contains(i)==false) ht.Add(i,1);
            else ht[i] = (int)ht[i] + 1;
        }
        foreach(char i in ransomNote){
            if(ht.Contains(i)==false) ht.Add(i,-1);
			else ht[i] = (int)ht[i] - 1;			
        }
        foreach(DictionaryEntry i in ht){
            if((int)i.Value<0) return false;            
        }
        return true;
    }
}

複雜度分析：

• 時間複雜度：同Character Counting所花費的時間，因此為O(m+n)。
• 空間複雜度：雖然使用了Hashtable，但是最多也只會儲存26個字母，所以空間複雜度應為O(1)。

學習重點

• 字元操作。
• Hash Table應用。