LeetCode383-Ransom Note

题目

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Example:

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Note:

You may assume that both strings contain only lowercase letters.

分析

题意是检测ransomNote是否可由magazines组合而成,且magazines中的字母只能使用一次,可无顺序地取用,题意并非是要找匹配的子串。由于题目只在意最后能还是不能构成ransomNote,所以我们可以先统计magazines中所有出现的字母的频次于字母表letters中,再遍历ransomNote做自减操作,当字母的频次已经为0但仍需要该字母时,表明无法构造,返回false。若能成功结束循环,则表明匹配成功,返回true。

代码

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        
        //统计magazine中每个单词出现的次数
        int[] letters = new int[26];
        for (int i = 0; i < magazine.length(); i++)
            letters[magazine.charAt(i) - 'a']++;
            
        //检查ransomNote是否可以被构建
        for (int i = 0; i < ransomNote.length(); i++) {
            
            int pos = ransomNote.charAt(i) - 'a';
            if (letters[pos] == 0) //不够用
                return false;
            else
                letters[pos]--;
        }
        
        return true;
    }
}

Leave a Comment.