原文链接: https://leetcode-cn.com/problems/ransom-note

英文原文

Given two stings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

 

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

 

Constraints:

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote and magazine consist of lowercase English letters.

中文题目

为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。

给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。

如果可以构成，返回 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 <= 105
• ransomNote 和 magazine 由小写英文字母组成

通过代码

高赞题解

class Solution {

    public boolean canConstruct(String ransom, String magazine) {

        if (magazine.length() < ransom.length()) return false;

        int caps[] = new int[26];

        for (char c : ransom.toCharArray()) {

            int index = magazine.indexOf(c, caps[c - 'a']);

            if (index == -1)

                return false;

            caps[c - 97] = index + 1;

        }

        return true;

    }

}

这个写法真的很精妙，首先，是判定magazine的长度是否小于ransom，如果小于那么一定是false；之后，它实际上是遍历了ransom当中的所有字符，然后在caps中保存的并非是magazine中每类字母的个数，而是在对应当前字符c的magazine中每类字母应该遍历的起始位置，如果index == -1则表示在magazine中从caps指定的遍历位置开始没有找到一样的字符，则输出false；这个大佬的解题思路真的很有意思。

本人新手，欢迎各位大佬的讨论和指正。

这是我写的一个可能的运行过程，方便理解（ransom=aadd,magazine=cadaad）：

统计信息

通过次数	提交次数	AC比率
82846	135713	61.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
贴纸拼词	困难