救赎金

题目：救赎金

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解法-数组哈希表

思路：

  1. 定义record[26]数组，用于记录每个字母出现的次数

  2. 统计r中每个字母出现的次数，记录record对应的位置上，实现方式为record递增

  3. 统计m中每个字母出现的次数，实现方式为：record对应位置上递减

  4. 遍历record[26]，只要有record[i]>0,则说明m中的元素r中没有或比r中多，返回false

  5. 如果record[26]所有的值都<=0,则说明r可以从m中挑选字母组成（r中的字母m中都有，并且m中可以比r中多），符合题意！

复杂度：

  • 时间复杂度：
  • 空间复杂度：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool canConstruct(string r, string m) {
        //用于记录每个字母出现的次数
        int record[26] = {0};
        //记录r字符串中每个字母出现的次数
        for(int i = 0;i < r.length();i++){
            record[r[i] - 'a']++;
        }
        //将r对应位置的次数递减
        for(int i = 0;i < m.length();i++){
            record[m[i] - 'a']--;
        }
        for(int i = 0;i < 26;i++){
            //如果record有位置大于0，说明m中的元素r中没有或比r中多，返回false
            if(record[i]>0){return false;}
        }
        return true;
    }
};

语法小计

  1. 该题没有语法小计
    *
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。