Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

一、题目描述

• 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
• 如果可以，返回 true ；否则返回 false 。
• magazine 中的每个字符只能在 ransomNote 中使用一次。
• 示例 1：
  • 输入： ransomNote = “a”, magazine = “b”
  • 输出： false
• 示例 2：
  • 输入： ransomNote = “aa”, magazine = “ab”
  • 输出： false
• 示例 3：
  • 输入： ransomNote = “aa”, magazine = “aab”
  • 输出： true
• 提示：
  • 1 <= ransomNote.length, magazine.length <= Math.pow(10,5)
  • ransomNote 和 magazine 由小写英文字母组成

二、思路分析：

• ransomNote由magazine里面的字符构成的必要条件就是，ransomNote字符串是magazine字符串的子集
• 首先将字符串转化为更方便遍历的字符串数组形式
• 如果ransomNote里的字符在magazine存在，就将magazine里的这个字符截取出来保存
• 最后判断从magazine截取出来的字符长度是否和ransomNote相等
  • 如果长度相等，则ransomNote里的字符在magazine都能找到，返回true
  • 如果不想等，则ransomNote里的字符在magazine至少存在一个字符找不到，返回false

三、AC 代码：

function canConstruct(ransomNote: string, magazine: string): boolean {
    let ransomNoteArr = ransomNote.split('');
    let magazineArr = magazine.split('');
    let resultArr = [];
    for(let i = 0; i < ransomNoteArr.length; i++){
        for(let j = 0; j < magazineArr.length; j++){
            if(ransomNoteArr[i] === magazineArr[j]){
                resultArr.push(magazineArr.splice(j, 1)[0]);
                j--;
                break;
            }
        }
    }
    if(resultArr.length === ransomNoteArr.length){
        return true
    }
    return false
};
复制代码

四、总结：

• 注意一点就是数组splice方法会改变原数组长度，所以截取之后的循环参数j需要减去1
• 因为题目要求每个字符只能使用一次，所以一旦在magazine字符里找到第一个和ransomNote字符相等并截取后，应当立即退出当前循环遍历，否则后面再遇到相等字符会二次截取，所以截取后的 break操作很重要
• 还有其他复杂度低的方式，有需要可以去题解区看看