LeetCode面试题Day13|LC383 赎金信、LC290 单词规律

题目一：

指路：

. - 力扣（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;}
};