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
    Commented Apr 28, 2015 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. Commented Apr 28, 2015 at 16:38


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.