0383. Ransom Note (Easy)

Question

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.

1
2
3

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

分析/解題

繼時空旅人買賣股票( 0121 ) 及闖空門教學( 0198 , ** 0213**** )後，
我們這次要來寫勒索信** 啦！
有沒有覺得這一系列很實用？(大誤)

勒索信的構成很簡單，就是每個從雜誌上的字，
剪下來以後只能用一次 ，要用這些字去組出勒索信的內容。

所以這個就很簡單就可以處理啦！
我們可以先將所有雜誌上的字分門別類，
這邊還很貼心告訴我們全部只有小寫字母 ，
所以分成a-z即可，計算總共有的素材數量。

接下來用勒索信上的每個字來去檢驗，
每次都扣除掉對應的字母的計數，中間一旦有素材不夠，
表示已經沒辦法完成信件，即可回傳false，
否則整個迴圈完成的話表示可構成勒索信，則回傳true。

依此可以寫成程式碼。

Java

Java的部分，其實如要扣掉一些條件，
可以先檢查兩者的長度，magazine長度比較小時肯定無法完成勒索信。
由於題目的給定，我們可以不用HashMap，
僅用一個長度26的陣列來處理，index則用c - ‘a’ 來計算，
留意使用–table[c-‘a’]時由於先進行遞減 ，所以檢查條件是小於0。

Python

Python的部分，可以用dictionary作到類似的事情。
(list也可以，不過要自行用ord來轉換，和Java不同)
當然，我們也可以使用Counter或count來做更迅速的計算。
(註解提供了另外兩種leetcode上別人的解法)

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(len(ransomNote) + len(magazine))/O(1))
(空間複雜度因為依題目提示，key值固定最多26，
所以不因字串長而改變。)

「如果要求含大小寫/大小寫可混用/含標點符號等狀況呢？」
(依照所需使用HashMap或Dictionary，
並將共用的部分利用他們相減的距離歸到同類)
(在ASCII Code上，‘a’-’A’ == 32 )

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(接下來快要漲成下個價格啦XD)： ** https://hiskio.com/courses/319?promo_code=VEQZV7E**