[HackerRank] Preparation_Kit (10. Ransom Note) [Dictionaries & Hashmaps]

Harold is a kidnapper who wrote a ransom note, but now he is worried it will be traced back to him through his handwriting. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use only whole words available in the magazine. He cannotuse substrings or concatenation to create the words he needs.

Given the words in the magazine and the words in the ransom note, print Yes if he can replicate his ransom note exactly using whole words from the magazine; otherwise, print No.

Example
magagine = "attack at dawn" note = "Attack at dawn" 

The magazine has all the right words, but there is a case mismatch. The answer is No. 

Function Description

Complete the checkMagazine function in the editor below. It must print Yes if the note can be formed using the magazine, or No. 

checkMagazine has the following parameters: 

• string magazine[m]: the words in the magazine 
• string note[n]: the words in the ransom note 

Prints

• string: either Yes or No, return value is expected

 

// 잘못된 코드1: 시간복잡도 n*(2n: filter 함수 + n) // Contains는 내부적으로 Set(Hash-)이면 O(1), Array이면 O(n) => 3n^2

func checkMagazine(magazine: [String], note: [String]) -> Void {
    // Write your code here
    var isYes = true
    for str in note {
        if (magazine.filter{$0 == str}.count < note.filter{$0 == str}.count) {
            isYes = false
            break
        }
        if !magazine.contains(str) {
            isYes = false
            break
        }
    }
    if isYes { print("Yes") }
    else { print("No") }
}

 

// 잘못된 코드2: 시간복잡도 n + n^2

func checkMagazine(magazine: [String], note: [String]) -> Void {
    var words: [String: Int] = [:]
    for n in note {
        if words.contains{$0.key == n} {
            words[n]! += 1
        } else {
            words[n] = 1
        }
    }
    for w in words {
        if w.value > magazine.filter{$0 == w.key}.count {
            print("No")
            return
        }
    }    
    print("Yes")
}

 

//잘못된 코드3: Reduced Time Complexity. However, there is no need to use 'contains' function in dictionaries.

So, the time complexity is still n*n + n*n + n.

func checkMagazine(magazine: [String], note: [String]) -> Void {
    //1. make it to dictionaries
    
    var words: [String: Int] = [:]
    var mag: [String: Int] = [:]
    for n in note {
        if words.contains{$0.key == n} {
            words[n]! += 1
        } else {
            words[n] = 1
        }
    }
    
    for m in magazine {
        if mag.contains{$0.key == m} {
            mag[m]! += 1
        } else {
            mag[m] = 1
        }
    }

    for w in words {
        if let m = mag[w.key] {
            if m < w.value {
                print("No")
                return 
            }
        } else {
             print("No")
            return 
        }
    }    
    print("Yes")
}

 

// 수정 후, After make it clean & remove the contains(because, we can directly access to the value just by using the key)

//hashtable
func checkMagazine(magazine: [String], note: [String]) -> Void {
    //make it to dictionaries to reduce time complexity
    var words: [String: Int] = [:]
    var mag: [String: Int] = [:]
    let result: Bool = true
    
    for n in note {
        var v = words[n] ?? 0
        v += 1
        words[n] = v
    }
    
    for m in magazine {
        var v = mag[m] ?? 0
        v += 1
        mag[m] = v
    }

    for w in words {
        let tmp = mag[w.key] ?? 0
        if tmp < w.value {
            print("No")
            return
        }
    }    
    print("Yes")
}

// Passed

+Dictionary & Set are internally implemented using a hash table.

---

https://www.hackerrank.com/challenges/ctci-ransom-note/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps