I was asked a question

You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word out of the character list such that the score is maximum and the word is valid.

I could think of a solution involving a trie made out of dictionary and backtracking with available characters, but could not formulate properly. Does anyone know the correct approach or come up with one?

  • Just a guess, but this smells like NP. The right approach may simply be to try to get a good approximation of the maximum score. – Neil Apr 28 '15 at 9:52
  • Assuming the list is short (say, 7 characters), you could read through the dictionary. For every dictionary word you can make with your list of characters, calculate the score. If the score is higher than the previously saved word and score, save the current word and score. – Gilbert Le Blanc Apr 28 '15 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.