PattySung

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

<解題>

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

        for(int i = 0; i < magazine.length(); i++){
            cnt[magazine.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < ransomNote.length(); i++){
            char c = ransomNote.charAt(i);
            
            if(cnt[c - 'a'] == 0){
                // 如果 cnt 中對應的元素值為 0，表示無法構建，返回 false
                return false;
            }
            
            cnt[c - 'a']--;
        }

        return true;
    }
}

T: O(m+n) S: O(1)

Leetcode-383. Ransom Note

<解題>