0383 Ransom Note

Warning

This post is more than a year old. Information may be outdated.

Solved at: 230128

Question

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.

Solution

swift

class Solution {    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {        var map = [Character: Int]()        for (_, char) in magazine.enumerated() {            if map.keys.contains(char) {                print("(char) is in map")                map[char]! += 1            }            else {                print("(char) is not in map")                map[char] = 1            }        }
        for (_, char) in ransomNote.enumerated() {            if map.keys.contains(char) {                if map[char]! == 0 {                    return false                } else {                    map[char]! -= 1                }            } else {                return false            }        }        return true    }}

class Solution {    func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {        var map = [Character: Int]()        for (_, char) in magazine.enumerated() {            if map.keys.contains(char) {                print("(char) is in map")                map[char]! += 1            }            else {                print("(char) is not in map")                map[char] = 1            }        }
        for (_, char) in ransomNote.enumerated() {            if map.keys.contains(char) {                if map[char]! == 0 {                    return false                } else {                    map[char]! -= 1                }            } else {                return false            }        }        return true    }}

Results

Runtime 511 ms. Beats 5.8%
Memory 14.5 MB. Beats 61.68%

Complexity Analysis

Time: $O(n)$ Space: $O(n)$ -- we can say this $O(1)$ because there are only 26 possible keys

Takeaways

Dictionary with finite set of key possible is $O(1)$

Backlinks (1)

Coding Tests

Comments (0)