得分最高的单词集合

1255. 得分最高的单词集合

你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的任意属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
单词表 words 中每个单词只能计分（使用）一次。
根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

示例 1：

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], 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]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2：

输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], 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]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3：

输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"], 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]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。

提示：

1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i] 和 letters[i] 只包含小写的英文字母。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-02-26 11:01:35

func maxScoreWords(words []string, letters []byte, score []int) (ans int) {
    left := [26]int{}
    for _, c := range letters {
        left[c-'a']++
    }

    var dfs func(int, int)
    dfs = func(i, total int) {
        if i < 0 { // base case
            ans = max(ans, total)
            return
        }

        // 不选 words[i]
        dfs(i-1, total)

        // 选 words[i]
        for j, c := range words[i] {
            c -= 'a'
            if left[c] == 0 { // 剩余字母不足
                for _, c := range words[i][:j] { // 撤销
                    left[c-'a']++
                }
                return
            }
            left[c]-- // 减少剩余字母
            total += score[c] // 累加得分
        }

        dfs(i-1, total)

        // 恢复现场
        for _, c := range words[i] {
            left[c-'a']++
        }
    }
    dfs(len(words)-1, 0)
    return
}

func max(a, b int) int { if a < b { return b }; return a }

java 解法, 执行用时: 16 ms, 内存消耗: 41.4 MB, 提交时间: 2023-02-26 11:00:53

class Solution {
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int[] cnt = new int[26];
        for (int i = 0; i < letters.length; ++i) {
            cnt[letters[i] - 'a']++;
        }
        int n = words.length;
        int ans = 0;
        for (int i = 0; i < 1 << n; ++i) {
            int[] cur = new int[26];
            for (int j = 0; j < n; ++j) {
                if (((i >> j) & 1) == 1) {
                    for (int k = 0; k < words[j].length(); ++k) {
                        cur[words[j].charAt(k) - 'a']++;
                    }
                }
            }
            boolean ok = true;
            int t = 0;
            for (int j = 0; j < 26; ++j) {
                if (cur[j] > cnt[j]) {
                    ok = false;
                    break;
                }
                t += cur[j] * score[j];
            }
            if (ok && ans < t) {
                ans = t;
            }
        }
        return ans;
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 1.9 MB, 提交时间: 2023-02-26 11:00:37

func maxScoreWords(words []string, letters []byte, score []int) (ans int) {
	cnt := [26]int{}
	for _, c := range letters {
		cnt[c-'a']++
	}
	n := len(words)
	for i := 0; i < 1<<n; i++ {
		cur := [26]int{}
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				for _, c := range words[j] {
					cur[c-'a']++
				}
			}
		}
		ok := true
		t := 0
		for i, v := range cur {
			if v > cnt[i] {
				ok = false
				break
			}
			t += v * score[i]
		}
		if ok && ans < t {
			ans = t
		}
	}
	return
}

golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2022-12-07 18:15:44

func dfs(words []string,k int,n int,storage *[]int,ans *[]string,score []int,maxScore *int) {
    //如果某个字母剩余使用个数小于0直接return
	if !check(storage){
		return
	}
	if k == n{
		//fmt.Println(*ans)
		sum := 0
		for _,str := range *ans{
			for _,v := range  str{
				sum += score[v - 97]
			}
		}
		if sum > *maxScore{
			*maxScore = sum
		}
		return
	}
	//拼写该单词消耗字母
	cost(words[k],storage)
	*ans = append(*ans,words[k])
	dfs(words,k +1,n,storage,ans,score,maxScore)
	//不拼写该单词需要先还原消耗掉的字母
	recover(words[k],storage)
	*ans = (*ans)[:len(*ans) - 1]
	dfs(words,k +1,n,storage,ans,score,maxScore)
}

func check(storage *[]int)bool{
	for _,v := range *storage{
		if v < 0{
			return false
		}
	}
	return true
}

func cost(str string,storage *[]int){
	for _,v := range str{
		(*storage)[v - 97]--
	}
}

func recover(str string,storage *[]int){
	for _,v := range str{
		(*storage)[v - 97]++
	}
}


func maxScoreWords(words []string, letters []byte, score []int) int {
	ans := make([]string,0)
	storage := make([]int,26)
	for _,v := range letters{
		storage[v - 97]++
	}
	maxScore := 0
	dfs(words,0,len(words),&storage,&ans,score,&maxScore)
	return maxScore
}

python3 解法, 执行用时: 68 ms, 内存消耗: 15.4 MB, 提交时间: 2022-12-07 18:14:40

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        words = [collections.Counter(i) for i in words]#单词转字典
        letters = collections.Counter(letters)#字符集转字典
        l = len(words)
        
        @lru_cache(None)
        def dfs(state):#状态位
            d = {}#字符统计
            for i in range(l):
                if state >> i & 1 == 1:#如果已选
                    for k, v in words[i].items():#累加字符数
                        d[k] = d.get(k, 0) + v
                        if d[k] > letters.get(k, 0):#如果超过可选字符，返回0
                            return 0
            res = sum([score[ord(k) - 97] * d[k] for k in d])#当前已选字符的总得分
            for i in range(l):
                if state >> i & 1 == 0:#如果未选
                    res = max(res, dfs(state | 1 << i))#与继续挑选单词的结果取最大值
            return res
            
        return dfs(0)

python3 解法, 执行用时: 324 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-07 18:14:20

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        ans = 0
        cnt = Counter(letters)
        n = len(words)
        for i in range(1, 1<<n):
            st = ""
            for j in range(n):
                if i & (1<<j):
                    st += words[j]
            cur = Counter(st)
            if all(cur[k]<=cnt[k] for k in cur):
                sc = 0
                for k in cur:
                    sc += cur[k]*score[(ord(k)-ord("a"))]
                ans = ans if ans > sc else sc
        return ans

python3 解法, 执行用时: 44 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-07 18:14:09

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:

        def check(word):
            cur = 0
            for w in word:
                cur += score[ord(w) - ord('a')]
            return cur

        n = len(words)

        cnt = [Counter(w) for w in words]
        score = [check(w) for w in words]
        post = [0]*(n+1)
        for i in range(n-1, -1, -1):
            post[i] = post[i+1] + score[i]

        def dfs(pre, j):
            nonlocal ans
            if j == n:
                if pre > ans:
                    ans = pre
                return
            if pre + post[j] < ans:
                return 
            if all(cnt[j][k] <= letter[k] for k in cnt[j]):
                for k in cnt[j]:
                    letter[k] -= cnt[j][k]
                dfs(pre + score[j], j + 1)
                for k in cnt[j]:
                    letter[k] += cnt[j][k]
            dfs(pre, j + 1)
            return

        letter = Counter(letters)
        ans = 0
        dfs(0, 0)
        return ans

上一题

下一题

详情