383. 赎金信

题目地址(383. 赎金信)

https://leetcode-cn.com/problems/ransom-note/

题目描述

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
提示：
你可以假设两个字符串均只含有小写字母。

前置知识

公司

• 暂无

思路

这道题可以使用map来做 但是map的空间和时间的消耗都要比数组的要大 这道题给定的数组范围就是26个英文字母 所以说数组方式更加的简单有效
两种思路 原理相差不大
第一种 新建两个数组 让两个数组分别循环两个字符串 将每一个字符对应的数组位置++
然后判断赎金信需要的字符是否大于杂志上的字符 如果大于的话就说明无法构成 返回false
第二种 定义一个temp 将杂志的字符串循环++ 然后在赎金信中判断需要的字符对应的数组位置的数字是否大于0 如果大于 就将该数字— 反之就说明不满足条件 返回false

关键点

代码

• 语言支持：Java

Java Code:

    public boolean canConstruct(String ransomNote, String magazine) {
            int[] record = new int[26];
            int[] record1 = new int[26];
            for (char aChar : magazine.toCharArray()) {
                record[aChar - 'a'] += 1;
            }
            for (char c : ransomNote.toCharArray()) {
                record1[c - 'a'] +=1;
            }
            for (int i = 0; i < 26; i++) {
                if (record[i]<record1[i]){
                    return false;
                }
            }
            return true;
        }

class Solution {
        public boolean canConstruct(String ransomNote, String magazine) {
            int[] record = new int[26];
            int temp ;
            for (int i = 0; i < magazine.length(); i++) {
                temp = magazine.charAt(i) - 'a';
                record[temp]++;
            }
            for (int i = 0; i < ransomNote.length(); i++) {
                temp = ransomNote.charAt(i) - 'a';
                if (record[temp]>0){
                    record[temp]--;
                }else {
                    return false;
                }
            }
            return true;
        }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=Mx0Ub)
• 空间复杂度：#card=math&code=O%28n%29&id=iyEiM)