383. Ransom Note

Problem

Đề bài yêu cầu kiêm tra xem có thể tạo ra chuỗi ransomNote từ các ký tự trong chuỗi magazine hay không, với mỗi ký tự trong magazine chỉ được dùng một lần

Approach

Đếm số lần xuất hiện của từng ký tự trong magazine

Duyệt qua từng ký tự trong ransomeNote , kiểm tra xem có đủ số lượng ký tự đó trong magazine không

Nếu thiếu bất kỳ ký tự nào, return false , Nếu đủ hết, return true

Time and space complexity

TC: O(m +n) với m là độ dài magazine , n là độ dài ransomNote

SC: O(1) nếu dùng Array(26), O(k) với k là số ký tự khác nhau nếu dùng Map

Solution

typescripttypescript

1function canConstruct(ransomNote: string, magazine: string): boolean {
2    const letter_count = Array(26).fill(0);
3    for (const char of magazine) {
4        const idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
5        letter_count[idx]++;
6    }
7
8    for (const char of ransomNote) {
9        const idx = char.charCodeAt(0) - 'a'.charCodeAt(0);
10        letter_count[idx]--;
11        if (letter_count[idx] < 0) return false
12    }
13
14    return true;
15};

Loading content...