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