题目一:
指路:
. - 力扣(LeetCode)383 赎金信
思路与分析:
判断一个字符串中的字符能否由另一个字符串内的内容组成。也就是说现在我们手里有一些字母若干个,拿这些字母能否拼成所需要的东西。根据题意,我们有的是magazine中的字母,判断能否拼成ransomNote中的字母。那么我们判断的是在magazine中字母出现的频次,如果对应在ransomNote中对应字母出现的频次小于等于magazine中的频次,那么返回true,否则返回false。在这里我们定义一个哈希表,因为题目中说两封信皆有小写字母构成,也就是最多只有26个字母变换频次。那么定义一个26大小的哈希表,首先遍历我们有的字母也就是magazine中的字母,使其对应字母的频次增加。其次,遍历需要构成的ransomNote,如果其中也有我们遍历进哈希表的字母,则使哈希表中对应字母频次-1,最后如果频次<0则说明我们手头的字母不够拼成赎金信返回false,否则返回true。
代码:
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int has[26];for (int i = 0; i < magazine.size(); i++) {has[magazine[i] - 'a']++; // 手里有这些字母}for (int i = 0; i < ransomNote.size(); i++) {has[ransomNote[i] - 'a']--; // 能不能构成这些if (has[ransomNote[i] - 'a'] < 0) return false;}return true;}
};
题目二:
指路:
. - 力扣(LeetCode)290 单词规律
思路与分析:
第一个字符串中的一个字母对应第二个字符串中的一个单词,此为双射。用哈希表记录字符对应的单词,枚举二者的配对更新哈希表的值。
代码:
class Solution {
public:bool wordPattern(string pattern, string s) {unordered_map<string, char> s2p;unordered_map<char, string> p2s;int i = 0;int n = s.length();for (char c : pattern) {if (i >= n)return false;int j = i;while (j < n && s[j] != ' ') j++;const string &tmp = s.substr(i, j - i);if (s2p.count(tmp) && s2p[tmp] != c) {return false;}if (p2s.count(c) && p2s[c] != tmp) {return false;}s2p[tmp] = c;p2s[c] = tmp;i = j + 1;}return i >= n;}
};