描述
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
分析
实际上就是验证 ransomNote 是否为 magazine 的子集,如果不用 Python,比较容易想到的方法是用哈希表,先将 magazine 这个字符串做一个映射,key 是字符的 ascii 码,value 是字符的个数,再遍历 ransomNote,遇到对应的字符,则 value 减1,如有<0的情况,则返回 false。
解决方案1(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : bool canConstruct (string ransomNote, string magazine) { int map_char_int[26 ] = {0 }; for (int i=0 ; i < magazine.length(); ++i) { ++map_char_int[magazine[i]-'a' ]; } for (int i=0 ; i < ransomNote.length(); ++i) { if ((--map_char_int[ransomNote[i]-'a' ]) < 0 ) { return false ; } } return true ; } };
利用 C艹 的特性,我们可以写得简练一点:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : bool canConstruct (string ransomNote, string magazine) { vector <int > letter_map (128 , 0 ) ; for (char item : magazine) { letter_map[item]++; } for (char item : ransomNote) { if (--letter_map[item] < 0 ) { return false ; } } return true ; } };
解决方案2(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class Solution { public boolean canConstruct (String ransomNote, String magazine) { int [] map_char_int = new int [26 ]; for (int i = 0 ; i < magazine.length(); i++) { map_char_int[magazine.charAt(i)-'a' ]++; } for (int i = 0 ; i < ransomNote.length(); i++) { if (--map_char_int[ransomNote.charAt(i)-'a' ] < 0 ) { return false ; } } return true ; } }
解决方案3(Python)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution (object) : def canConstruct (self, ransomNote, magazine) : """ :type ransomNote: str :type magazine: str :rtype: bool """ ransomNoteSet, magazineSet = set(ransomNote), set(magazine) if not ransomNoteSet.issubset(magazineSet): return False for item in ransomNoteSet: if ransomNote.count(item) > magazine.count(item): return False return True
相关问题