Epoch

問題

  Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magines; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:

You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

想法

  原先要找一一對應，甚至還用排序，但是發生 TLE；想到只要用個陣列存 a~z 出現的次數，可以更有效率。但還是一直 TLE，看看討論區的程式碼，還是不懂為什麼會造成 TLE，最後發現是 strlen 這個 function 造成 TLE，於是改寫後就順利通過。

code

bool canConstruct(char* ransomNote, char* magazine) {
    int i=0;
    int *keys = malloc(26 * sizeof(int));
    memset(keys, 0, 26 * sizeof(int));
    for(i=0; magazine[i]!='\0'; i++){
       keys[(int)magazine[i]-'a']++;
    }
    for(i=0; ransomNote[i]!='\0'; i++){
        if(keys[(int)ransomNote[i]-'a']>0)
            keys[(int)ransomNote[i]-'a']--;
        else
            return false;
    }
    return true;
}