[leetcode #383] Ransom Note

Problem

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters 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 <= 10⁵
· ransomNote and magazine consist of lowercase English letters.

Idea

magazine을 구성하는 문자들로 ransomNote를 만들 수 있는 지 확인하는 문제다.

두 문자열 모두 알파벳 소문자로 구성되어 있으므로 크기가 26인 배열을 만들어 각 문자의 개수를 센다.
ransomNote의 특정 알파벳 수가 magazine의 것보다 크다면 ransomNote를 만들 수 없다는 의미이므로 false를 리턴한다.
모든 알파벳에 대한 검증이 끝나면 true를 리턴한다.

Solution

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] ransomNoteCnt = new int[26];
        int[] magazineCnt = new int[26];

        for (int i=0; i < ransomNote.length(); i++) {
            ransomNoteCnt[ransomNote.charAt(i) - 'a']++;
        }

        for (int i=0; i < magazine.length(); i++) {
            magazineCnt[magazine.charAt(i) - 'a']++;
        }

        for (int i=0; i < 26; i++) {
            if (ransomNoteCnt[i] > magazineCnt[i]) {
                return false;
            }
        }

        return true;
    }
}

Reference

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