Thursday, August 04, 2016

find longest words in words formed by chars

words = [ "abc" , "baa" , "caan" , "an" , "banc" ]
chars = [ "a" , "a" , "n" , "c" , "b"]

output = ["caan", "banc"]

Two optimizations:
1. canFormWord() returns false when word's length is lesser than chars's length
2. canFormWord() is called only if word's length() is >= maxlen
(words, chars):
    // nulls checks omitted
    list longest = new
    charsmap = tocharmap(chars)
    maxlen = 0
    for word in words:
        if word.length() >= maxlen && canFormWord(charsmap, word, chars):
            if word.length() > maxlen:
                longest.clear()
                maxlen = word.length()
            if word.length() == maxlen:
                longest.add(word)
    return longest

tocharmap(chars):
    charsmap = new
    for c in chars:
        count = 0
        charsmap.tryget(c, out count)            
        charsmap[c] = count+1
    return charsmap

// return false early if word's char is not present in charsmap or
// if char's count is less in charsmap
canFormWord(charsmap, word, chars):
    if chars.length() < word.length():
        return false
    result = true
    wordmap = new
    for c in word:
        if !charsmap.haskey(c):
            result = false
            break
        count = 0
        wordmap.trygetvalue(c, out count)
        count++
        wordmap[c] = count
        if charsmap[c] < count:
            result = false
            break
    return result
[Hat tip to SM]

No comments:

Post a Comment