題目:給定一個贖金信 (ransom) 字串和一個雜誌(magazine)字串,判斷第一個字串 ransom 能不能由第二個字串 magazines 裡面的字元構成。如果可以構成,返回 true ;否則返回 false。
(題目說明:為了不暴露贖金信字跡,要從雜誌上搜索各個需要的字母,組成單詞來表達意思。雜誌字串中的每個字元只能在贖金信字串中使用一次。)
注意:你可以假設兩個字串均只含有小寫字母。
canConstruct("a", "b") -> falsecanConstruct("aa", "ab") -> falsecanConstruct("aa", "aab") -> true
解題:用一個數組 chars 存放 magazine 中每個字母出現的次數。遍歷 ransomNote 中每個字母,判斷 chars 是否包含即可。
class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] chars = new int[26]; for (int i = 0, n = magazine.length(); i < n; ++i) { int idx = magazine.charAt(i) - 'a'; ++chars[idx]; } for (int i = 0, n = ransomNote.length(); i < n; ++i) { int idx = ransomNote.charAt(i) - 'a'; if (chars[idx] == 0) return false; --chars[idx]; } return true; }}
最新評論