問題：

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 magazines ; 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

大意：

給出一個任意的勒索信字符串和另一個的包含所有從雜志中來的字母的字符串，寫一個函數(shù)，如果勒索信可以被雜志重構(gòu)得到則返回true；否則返回false。
雜志中的每個字母都只能被使用一次。
注意：
你可以假設(shè)字符串都只包含小寫字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

思路：

1. 首先想到的一個思路是以各個地在magazine中尋找note中的字母，找到一個則刪去一個，若有找不到的就是false了，若找到最后一個都找到了，則是true了。
2. 第一個思路做出來后，運行時間高達(dá)91ms，想來是每個字母的尋找過程都比較耗時，于是參照以前的經(jīng)驗，對于這種全是小寫字母進(jìn)行比較字符串的，還是可以拿兩個26位的數(shù)字?jǐn)?shù)組來存儲兩個字符串中每個字母找到的個數(shù)，然后去比較兩個數(shù)字?jǐn)?shù)組中的數(shù)字，不同的是，這里要比較的是note對應(yīng)的數(shù)組中，不為0的字母位置的數(shù)字，在magazine數(shù)組中的數(shù)字是否大于note中的數(shù)字，注意是大于而不是等于，因為目的是magazine可以拼出note來，而不是完全相同，這樣一來耗時迅速減少到了17ms，優(yōu)化很明顯。

代碼（Java）：

第一種方法：

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] noteArr = new char[ransomNote.length()];
        noteArr = ransomNote.toCharArray();
        for (int i = 0; i < noteArr.length; i++) {
            if (magazine.indexOf(noteArr[i]) == -1) return false;
            else {
                int position = magazine.indexOf(noteArr[i]);
                String before = magazine.substring(0, position);
                String after = magazine.substring(position+1, magazine.length());
                magazine = before.concat(after);
            }
        }
        return true;
    }
}

第二種方法：

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] noteArr = new char[ransomNote.length()];
        noteArr = ransomNote.toCharArray();
        char[] magazineArr = new char[magazine.length()];
        magazineArr = magazine.toCharArray();
        // int數(shù)組默認(rèn)會初始化為全為0
        int[] noteLetter = new int[26];
        int[] magazineLetter = new int[26];
        for (int i = 0; i < noteArr.length; i++) {
            int position = noteArr[i] - 'a';
            noteLetter[position]++;
        }
        for (int i = 0; i < magazineArr.length; i++) {
            int position = magazineArr[i] - 'a';
            magazineLetter[position]++;
        }
        for (int i = 0; i < 26; i++) {
            if (noteLetter[i] != 0 && noteLetter[i] > magazineLetter[i]) return false;
        }
        return true;
    }
}

查看作者首頁