0

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?

Improve this question
2
  • 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, 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.
    – Gilbert Le Blanc
    Apr 28, 2015 at 16:38

0

Reset to default

Your Answer

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