<p>Given a list of <code>words</code>, list of&nbsp; single&nbsp;<code>letters</code> (might be repeating)&nbsp;and <code>score</code>&nbsp;of every character.</p>

<p>Return the maximum score of <strong>any</strong> valid set of words formed by using the given letters (<code>words[i]</code> cannot be used two&nbsp;or more times).</p>

<p>It is not necessary to use all characters in <code>letters</code> and each letter can only be used once. Score of letters&nbsp;<code>&#39;a&#39;</code>, <code>&#39;b&#39;</code>, <code>&#39;c&#39;</code>, ... ,<code>&#39;z&#39;</code> is given by&nbsp;<code>score[0]</code>, <code>score[1]</code>, ... , <code>score[25]</code> respectively.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;dog&quot;,&quot;cat&quot;,&quot;dad&quot;,&quot;good&quot;], letters = [&quot;a&quot;,&quot;a&quot;,&quot;c&quot;,&quot;d&quot;,&quot;d&quot;,&quot;d&quot;,&quot;g&quot;,&quot;o&quot;,&quot;o&quot;], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
<strong>Output:</strong> 23
<strong>Explanation:</strong>
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words &quot;dad&quot; (5+1+5) and &quot;good&quot; (3+2+2+5) with a score of 23.
Words &quot;dad&quot; and &quot;dog&quot; only get a score of 21.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;xxxz&quot;,&quot;ax&quot;,&quot;bx&quot;,&quot;cx&quot;], letters = [&quot;z&quot;,&quot;a&quot;,&quot;b&quot;,&quot;c&quot;,&quot;x&quot;,&quot;x&quot;,&quot;x&quot;], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
<strong>Output:</strong> 27
<strong>Explanation:</strong>
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words &quot;ax&quot; (4+5), &quot;bx&quot; (4+5) and &quot;cx&quot; (4+5) with a score of 27.
Word &quot;xxxz&quot; only get a score of 25.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;leetcode&quot;], letters = [&quot;l&quot;,&quot;e&quot;,&quot;t&quot;,&quot;c&quot;,&quot;o&quot;,&quot;d&quot;], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
<strong>Output:</strong> 0
<strong>Explanation:</strong>
Letter &quot;e&quot; can only be used once.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 14</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 15</code></li>
	<li><code>1 &lt;= letters.length &lt;= 100</code></li>
	<li><code>letters[i].length == 1</code></li>
	<li><code>score.length ==&nbsp;26</code></li>
	<li><code>0 &lt;= score[i] &lt;= 10</code></li>
	<li><code>words[i]</code>, <code>letters[i]</code>&nbsp;contains only lower case English letters.</li>
</ul>

'''
算法原理解释
这个算法的核心思想是使用位运算来枚举所有可能的单词组合，并判断哪些组合可以用给定的字母构成，
然后计算这些组合的分数，最终返回最高分数。

组合枚举：通过使用 1 << n 来生成所有可能的单词组合。1 << n 实际上是 2^n，对应的 m 
就表示从 0 到 2^n - 1 的所有整数，每个整数的二进制表示可以用来表示一个单词组合。
例如，0011 表示选择了第 0 和第 1 个单词。

判断合法性：对于每个组合，使用 Counter 对字母的可用数量进行计数。然后遍历每个单词，
检查这个单词中的每个字母是否可以被当前的字母列表所支持。如果不能支持，则标记该组合无效，并停止计算该组合的分数。

计算分数：如果组合是有效的，那么根据单词中的字母得分来计算组合的总分数。

更新最大值：对每个有效的组合分数进行比较，更新最大分数。

时间复杂度分析
枚举组合的复杂度：共有 2^n 个可能的组合，因此时间复杂度为 O(2^n)。
检查每个组合的复杂度：对于每个组合，最多要检查 n 个单词，每个单词的最大长度为 L，因此检查一个组合的复杂度为 O(n * L)。
总复杂度：整体复杂度为 O(n * L * 2^n)。由于 n 最大为 14，复杂度在可接受范围内。
这个算法通过枚举所有可能的组合，并对每个组合进行合法性验证和分数计算，从而找到最高的分数。
'''

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        n = len(words)  # 获取单词列表的长度
        m = 1 << n  # 计算所有可能的单词组合数量，使用位运算表示，1 << n 相当于 2^n

        f = defaultdict(int)  # 创建一个字典，用于存储每个组合的分数，默认值为0
        res = -1  # 初始化最大分数为-1
        for i in range(1, m):  # 遍历所有可能的组合，从1开始，因为0代表不选取任何单词
            cnt = Counter(letters)  # 统计每个字母的可用数量
            flag = True  # 标志位，用于判断当前组合是否有效
            for j in range(n):  # 遍历每个单词，判断该单词是否在当前组合中
                if (i) & 1 << j and flag:  # 检查第 j 个单词是否在当前组合中（通过位运算）
                    for c in words[j]:  # 遍历单词中的每个字母
                        if cnt[c] == 0:  # 如果字母不够用
                            f[i] = 0  # 当前组合无效，分数为0
                            flag = False  # 置标志位为False，结束该组合的计算
                            break  # 跳出循环，不再处理当前单词
                        cnt[c] -= 1  # 如果字母足够用，减少字母的计数
                        f[i] += score[ord(c)-ord('a')]  # 增加该单词的分数
                if not flag:  # 如果当前组合无效，跳出循环
                    break

            res = max(res, f[i])  # 更新最大分数

        return res  # 返回最大分数

17900