CareerCup

Store dictionary words in a trie for fast membership tests (much more memory efficient than a hash table).

For each letter, find the highest score possible for a word starting with that letter. Do this by first looking up that letter in the trie, then recursively looking up all possible follow-up letters. This will minimize the number of words which are considered which are not in the dictionary.

// scores Letter <-> score
map<char, int> scores;

// sort function
bool byScore(char c1, char c2) {
	if (scores[c1] > scores[c2]) {
		return true;
	} 
	if (scores[c1] < scores[c2]) {
		return false;
	}
	return c1 > c2;
}

// get the score of the dictionary word
int getWordScore(string word) {
	int score = 0;
	for (int i=0; i<(int)word.size(); i++) {
		score += scores[word[i]];
	}
	return score;
}
int getMaxScoreHelper(char *tiles, int len, set<string> voc, string word, string prefix) {
	int maxScore = -1;
	for (int i=0; i<len; i++) {
		string newWord = prefix;
		newWord += tiles[i];
		// check if the word exists in the dictionary
		if (voc.find(newWord) != voc.end()) {
			int score  = getWordScore(newWord);
			if (score > maxScore) {
				maxScore = score;
				word = newWord;
			}
		}
		char leftTiles[7];
		for (int j=0, k=0; j<len; j++) {
			if (i != j) {
				leftTiles[k] = tiles[j];
				k++;
			}
		}
		// check if the word can be "extended"
		score = getMaxScoreHelper(leftTiles, len-1, voc, word, newWord);
		if (score > maxScore) {
			maxScore = score;
		}
	}
	return maxScore;
}
// get the max word and score
// input: tiles, dictionary, output word
// return score, -1 if no word found
int getMaxScore(char tiles[], set<string> voc, string &word) {
	sort(tiles, tiles+7, byScore);	
	
	word = "";
	return getMaxScoreHelper(tiles, 7, voc, word, "");
}