arcbjorn

thoughtbook

RSS Feed

Thursday, December 22, 2022

Ransom note

Leetcode 383 problem.

A function to determine if ransomNote can be constructed by using the letters from magazine, each of them is used only once.

Go

  • Time complexity: O(nk)O(n*k) - n is a length of the first string, k is a length of the second string (if it's larger than n)
  • Auxiliary space: O(1)O(1) - constant amount of space
import "strings"

func canConstruct(ransomNote string, magazine string) bool {
    for _, rune := range ransomNote {
        frequencyInRansomNote := strings.Count(ransomNote, string(rune))
        frequencyInMagazine := strings.Count(magazine, string(rune))

        if (frequencyInMagazine < frequencyInRansomNote) {
            return false
        }
    }

    return true
}
Creative Commons Licence