383. Ransom Note

Easy

Hashmap

Problem

İki string verilmiştir: ransomNote ve magazine. ransomNote stringi magazine'deki harfler kullanılarak oluşturulabiliyorsa true, aksi halde false döndürün.

magazine'deki her harf ransomNote'da yalnızca bir kez kullanılabilir.

Örnek 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Örnek 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Örnek 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

Kısıtlamalar:

1 <= ransomNote.length, magazine.length <= 10⁵
ransomNote ve magazine yalnızca küçük İngilizce harflerden oluşur.

Çözümler

Çözüm 1: İki Dictionary Yaklaşımı

Bu yaklaşımda her iki string için ayrı dictionary oluşturuyoruz ve karşılaştırıyoruz. Her karakterin sayısını saklayıp, ransomNote'daki her karakter için magazine'de yeterli olup olmadığını kontrol ediyoruz.

class Solution {
    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
        var dictRansomNote: [Character: Int] = [:]
        var dictMagazine: [Character: Int] = [:]
        
        for letter in ransomNote {
            if dictRansomNote[letter] == nil {
                dictRansomNote[letter] = 1
            } else {
                dictRansomNote[letter]! += 1
            }
        }

        for letter in magazine {
            if dictMagazine[letter] == nil {
                dictMagazine[letter] = 1
            } else {
                dictMagazine[letter]! += 1
            }
        }

        for (key, value) in dictRansomNote {
            if dictMagazine[key] != nil {
                if value > dictMagazine[key]! {
                    return false
                }
            } else {
                return false
            }
        }

        return true
    }
}

Time Complexity: O(m + n) Space Complexity: O(k)

m = magazine uzunluğu, n = ransomNote uzunluğu, k = benzersiz karakter sayısı (en fazla 26)

Çözüm 2: Tek Dictionary Yaklaşımı (Optimize)

Bu yaklaşımda sadece magazine'deki karakterleri sayıyoruz. Ardından ransomNote'daki her karakter için dictionary'den düşüyoruz. Eğer herhangi bir karakter için sayı sıfırın altına düşerse, false döndürüyoruz.

class Solution {
    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
        // Magazine'deki karakter sayılarını tutan dictionary
        var charCount: [Character: Int] = [:]
        
        // Magazine'deki her karakteri say
        for char in magazine {
            charCount[char, default: 0] += 1
        }
        
        // RansomNote'daki her karakter için kontrol et
        for char in ransomNote {
            // Karakter yoksa veya tükendiyse false döndür
            guard let count = charCount[char], count > 0 else {
                return false
            }
            charCount[char] = count - 1
        }
        
        return true
    }
}

Time Complexity: O(m + n) Space Complexity: O(k)

Tek dictionary kullanarak hafıza kullanımını yarıya indiriyoruz.

Çözüm 3: Array Tabanlı Yaklaşım

Sadece küçük İngilizce harfler olduğu için, 26 elemanlı sabit boyutlu bir array kullanabiliriz. Bu yaklaşım dictionary'ye göre daha hızlıdır çünkü hash hesaplaması yapmaz.

class Solution {
    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
        // 26 harf için sabit boyutlu array (a=0, b=1, ..., z=25)
        var letterCount = [Int](repeating: 0, count: 26)
        let aAscii = Character("a").asciiValue!
        
        // Magazine'deki harfleri say
        for char in magazine {
            let index = Int(char.asciiValue! - aAscii)
            letterCount[index] += 1
        }
        
        // RansomNote için kontrol et
        for char in ransomNote {
            let index = Int(char.asciiValue! - aAscii)
            letterCount[index] -= 1
            
            // Negatife düştüyse, yeterli harf yok
            if letterCount[index] < 0 {
                return false
            }
        }
        
        return true
    }
}

Time Complexity: O(m + n) Space Complexity: O(1)

Array boyutu sabit 26 olduğu için alan karmaşıklığı O(1) kabul edilir.

Çözüm 4: Erken Çıkış Optimizasyonu

Eğer ransomNote uzunluğu magazine uzunluğundan büyükse, hiçbir şekilde oluşturulamaz. Bu basit kontrol ile gereksiz işlemlerden kaçınabiliriz.

class Solution {
    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
        // Erken çıkış: ransomNote daha uzunsa imkansız
        guard ransomNote.count <= magazine.count else {
            return false
        }
        
        var letterCount = [Int](repeating: 0, count: 26)
        let aAscii = Character("a").asciiValue!
        
        // Magazine'deki harfleri say
        for char in magazine {
            letterCount[Int(char.asciiValue! - aAscii)] += 1
        }
        
        // RansomNote için kontrol et
        for char in ransomNote {
            let index = Int(char.asciiValue! - aAscii)
            letterCount[index] -= 1
            if letterCount[index] < 0 {
                return false
            }
        }
        
        return true
    }
}

Time Complexity: O(m + n) Space Complexity: O(1)

En kötü durumda aynı ama bazı durumlarda erken çıkış ile O(1) olabilir.

Çözüm 5: Fonksiyonel Yaklaşım (reduce)

Swift'in reduce fonksiyonunu kullanarak daha fonksiyonel bir yaklaşım. Kod daha kısa ama performans açısından dictionary çözümüyle aynı.

class Solution {
    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
        // Magazine'den karakter sayılarını oluştur
        var charCount = magazine.reduce(into: [Character: Int]()) { counts, char in
            counts[char, default: 0] += 1
        }
        
        // RansomNote'u kontrol et
        for char in ransomNote {
            guard let count = charCount[char], count > 0 else {
                return false
            }
            charCount[char]! -= 1
        }
        
        return true
    }
}

Time Complexity: O(m + n) Space Complexity: O(k)

Daha Swift idiomatik ama dictionary overhead'i var.

Önemli Noktalar

HashMap vs Array: Sadece 26 küçük harf olduğunda, sabit boyutlu array kullanmak daha verimlidir.
Erken Çıkış: Basit kontroller (uzunluk karşılaştırması) performansı artırabilir.
ASCII Dönüşümü: Swift'te asciiValue kullanarak karakter-index dönüşümü yapılır.
Silme vs Sayma: Karakterleri silmek yerine sayıları azaltmak daha verimlidir.