383.md

383. Ransom Note

Description

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.

Note: You may assume that both strings contain only lowercase letters.

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

Thinking Process

1. Scan through the magazine, maintain a table freq storing the frequence of each letter
2. Scan through the ransomNote, return false if at any point freq[c] == 0

Code

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

Complexity

1. Space complexity is O(1) as we only use constant extra space
2. Time complexity is O(n + m) as both the magazine and the ransomNote are scanned once