得分最高的单词集合【LC1255】
你将会得到一份单词表
words，一个字母表letters（可能会有重复字母），以及每个字母对应的得分情况表score。请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由
letters里的字母拼写出的 任意 属于words单词子集中，分数最高的单词集合的得分。单词拼写游戏的规则概述如下：
- 玩家需要用字母表
letters里的字母来拼写单词表words中的单词。- 可以只使用字母表
letters中的部分字母，但是每个字母最多被使用一次。- 单词表
words中每个单词只能计分（使用）一次。- 根据字母得分情况表
score，字母'a','b','c', … ,'z'对应的得分分别为score[0],score[1], …,score[25]。- 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。
就是被困难题吓了一跳
- 思路：
回溯枚举每一种子集情况，如果字母表的字母可以组成该子集的多所有单词，那么记录并更新分数，最后返回最大值 - 回溯三部曲
- 回溯函数模板返回值以及参数
- path（当前已经获得的分数），i（记录本层递归中，从哪个字符串开始遍历）
- 全局变量：(存放符合条件单一结果)，res(存放符合条件的单词子集的最大分数)，words，score
- 回溯函数终止条件
- 当搜索到单词表的末尾时，更新结果并返回
- 回溯搜索的遍历过程：分两种情况考虑
- 不选择单词words[i]，直接递归到下一个单词
- 选择单词words[i]，剩余字母表存量能够存放该单词时，才能搜索下一个单词，递归结束后需要回溯
class Solution { int res; int[] counts, score; String[] words; public int maxScoreWords(String[] words, char[] letters, int[] score) { this.score = score; this.words = words; res = 0; counts = new int[26]; for (char letter : letters){ counts[letter - 'a']++; } backtracking(0, 0); return res; } public void backtracking(int path, int i){ if (i == words.length){ res = Math.max(res, path); return; } // 不选words[i] backtracking(path, i + 1); // 选words[i] boolean flag = true; for (char c : words[i].toCharArray()){ counts[c - 'a']--; path += score[c - 'a']; if (counts[c - 'a'] < 0){ flag = false; } } if (flag){ backtracking(path, i + 1); } // 回溯 for (char c : words[i].toCharArray()){ counts[c - 'a']++; } } }
