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