LeetCode 1255 - Maximum Score Words Formed by Letters

https://leetcode.com/problems/maximum-score-words-formed-by-letters/

Given a list of words, list of  single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

Example 1:

Input: 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]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

Example 2:

Input: 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]
Output: 27
Explanation:
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.

Example 3:

Input: 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]
Output: 0
Explanation:
Letter "e" can only be used once.

Constraints:

• 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] contains only lower case English letters

X. https://www.acwing.com/solution/LeetCode/content/6125/

(二进制枚举) $O(n\cdot {\mathrm{2^}}^n)$

1. 枚举二进制的集合，从 1 到 $2^n-1$。
2. 每一位 0 或 1 代表选或不选。

时间复杂度

• 需要 $O(2^n)$ 种情况全部枚举，每次枚举后需要 $O(n)$ 的时间找到被选出的单词，故时间复杂度为 $O(n\cdot {\mathrm{2^}}^n)$。

空间复杂度

• 仅需要常数的额外空间。

    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        int n = words.size();
        int ans = 0;

        vector<int> valid(26, 0);
        for (char c : letters)
            valid[c - 'a']++;

        for (int S = 1; S < (1 << n); S++) {
            vector<int> used(26, 0);
            int tot = 0;
            for (int i = 0; i < n; i++)
                if ((S >> i) & 1) {
                    for (char c : words[i]) {
                        used[c - 'a']++;
                        tot += score[c - 'a'];
                    }
                }

            bool flag = true;
            for (int i = 0; i < 26; i++)
                if (used[i] > valid[i]) {
                    flag = false;
                    break;
                }

            if (flag)
                ans = max(ans, tot);
        }

        return ans;
    }




X.
https://www.icode9.com/content-4-554788.html

用回溯法遍历各种可能性，时间复杂度 O（2^n），可以使用一些剪枝的技巧。

private static int result;
    private static Map<String, Integer> scoreMap = null;
    private static int[] lettersNumber;

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        result = 0;
        scoreMap = new HashMap<>();
        lettersNumber = new int[26];
        char[] chars;
        int wordScore;
        for (String word : words) {
            chars = word.toCharArray();
            wordScore = 0;
            for (char aChar : chars) {
                wordScore += score[aChar - 'a'];
            }
            scoreMap.put(word, wordScore);
        }
        for (char letter : letters) {
            lettersNumber[letter - 'a']++;
        }
        Arrays.sort(words, (a, b) -> scoreMap.get(b) - scoreMap.get(a));
        dfsHelper(0, 0, words);
        return result;
    }

    private void dfsHelper(int score, int index, String[] words) {
        if (index >= words.length) {
            result = Math.max(result, score);
            return;
        }
        String word = words[index];
        if ((score + scoreMap.get(word) * (words.length - index)) <= result) {
            return;
        }
        char[] chars = word.toCharArray();
        int len = 0;
        for (char aChar : chars) {
            if (lettersNumber[aChar - 'a'] > 0) {
                lettersNumber[aChar - 'a']--;
                len++;
            } else {
                break;
            }
        }
        if (len == chars.length) {
            score += scoreMap.get(word);
            dfsHelper(score, index + 1, words);
            score -= scoreMap.get(word);
        }
        for (int i = 0; i < len; i++) {
            lettersNumber[chars[i] - 'a']++;
        }
        dfsHelper(score, index + 1, words);
    }

https://leetcode.com/problems/maximum-score-words-formed-by-letters/discuss/425129/java-backtrack-similar-to-78.-Subsets-1ms-beats-100

Similar to 78. Subsets, use backtrack to solve the problem.

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        if (words == null || words.length == 0 || letters == null || letters.length == 0 || score == null || score.length == 0) return 0;
        int[] count = new int[score.length];
        for (char ch : letters) {
            count[ch - 'a']++;
        }
        int res = backtrack(words, count, score, 0);
        return res;
    }
    int backtrack(String[] words, int[] count, int[] score, int index) {
        int max = 0;
        for (int i = index; i < words.length; i++) {
            int res = 0;
            boolean isValid = true;
            for (char ch : words[i].toCharArray()) {
                count[ch - 'a']--;
                res += score[ch - 'a'];
                if (count[ch - 'a'] < 0) isValid = false;
            }
            if (isValid) {
                res += backtrack(words, count, score, i + 1);
                max = Math.max(res, max);
            }
            for (char ch : words[i].toCharArray()) {
                count[ch - 'a']++;
                res = 0;
            }
        }
        return max;
    }

https://leetcode.jp/leetcode-1255-maximum-score-words-formed-by-letters-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90/

先看words数组中的单词能不能被拼写出来，这取决于letters数组中有没有相应足够多的字符，如果没有肯定是要被pass掉的，关键在于，如果letters数组中存在足够多的字符能够拼出当前单词，那么我们就要做出选择，是拼当前字符还是不拼，这两种选择哪种会导致全局结果更好，当前是无法得知的，因此要递归到子问题中继续求解。

解题步骤大概如下：

1. 先统计下letters数组中26个小写字母各有多少个。
2. 从words数组中第一个index的字符串开始递归，如果letters数组中没有足够多的字符能够组成当前字符串，index加一递归到下一层。
3. 反之，我们有两种选择，第一，将当前字符拼写出来，同时在letters数组中减去使用掉的字符数量，再算出当前字符串能够得到的积分，最后index加一递归到下一层。第二中选择是，我们不拼写当前字符串，直接index加一递归到下一层。比较两种选择结果更好的一方返回。
4. 递归结束条件为index到达words数组末尾。

public int maxScoreWords(String[] words, char[] letters, int[] score) {

    int[] letterCount = new int[26]; // 用来统计每个字符的个数

    // 统计每个字符的个数

    for(char c : letters) letterCount[c-'a']++;

    // 从第一个字符串开始递归

    return helper(words, letterCount, score, 0, 0);

}

// words：words数组

// letterCount：letters数组中每种字符的个数

// score：score数组

// sum：当前为止的累计得分

// index：当前index

int helper(String[] words, int[] letterCount, int[] score, int sum, int index){

    // 如果index达到数组末尾，递归结束，返回当前累计得分

    if(index == words.length) return sum;

    String word=words[index]; // 当前字符串

    int res = 0; // 返回结果（累计得分）

    // 如果存在足够的字符能够组成当前字符串

    if(hasWord(word, letterCount)){

        // 第一种选择：拼写出当前字符串

        int s=0; // 当前字符串能够拿到的分数

        // 循环字符串中每个字符

        for(int i=0;i<word.length();i++){

            // 消耗一个当前字符

            letterCount[word.charAt(i)-'a']--;

            // 累加分数

            s+=score[word.charAt(i)-'a'];

        }

        // sum加上当前字符串分数，index加一，递归到下一层

        res = helper(words, letterCount, score, sum+s, index+1);

        // 递归后将letterCount数组个数还原

        for(int i=0;i<word.length();i++){

            letterCount[word.charAt(i)-'a']++;

        }

    }

    // 第二种选择：不拼写出当前字符串，即直接index加一递归到下一层

    // 返回两种选择的最大值

    return Math.max(res, helper(words, letterCount, score, sum, index+1));

}

// 查看letterCount中是否含有足够的字符以能够组成字符串word

boolean hasWord(String word, int[] letterCount){

    int[] count = new int[26];

    for(int i=0;i<word.length();i++){

        count[word.charAt(i)-'a']++;

    }

    for(int i=0;i<26;i++){

        if(count[i]>letterCount[i]){

            return false;

        }

    }

    return true;

}

https://leetcode.com/problems/maximum-score-words-formed-by-letters/discuss/425104/Detailed-Explanation-using-Recursion

• Since the number of words is quite less (14), we can just generate all the subsets. Let's call a subset valid if all the words in that subset can be formed by using the given letters. It is clear that we need to maximize the score of valid subsets. To do this, we generate all subsets, and check if it is valid. If it is, we find its score and update the global maxima.
• To generate the subsets, we create a function call generate_subset(words, n) which generate all the subsets of the vector words. To quickly recap, we have 2 choices for the last element, either to take it or to leave it. We store this choice in an array called taken where taken[i] represent that the i-th element was taken in our journey. We then recurse for the remaining elements.
• When n becomes zero, it means we cannot make any more choices. So now, we traverse our taken array to find out the elements in this subset. Then we count the frequency of each letter in this subset. If the frequency of each letter is under the provided limit, it means it is a valid subet. Hence, we find the score of this subset and update the maxima

public:
    vector<bool> taken;
    vector<int> count;
    vector<int> score;
    int max_sum = 0;
    
    void update_score(vector<string>& words);
    void generate_subset(vector<string>& words, int n);
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score);
};

void Solution :: generate_subset(vector<string>& words, int n)
{
    if(n == 0)
    {
        update_score(words);
        return;
    }
    
    taken[n-1] = true;
    generate_subset(words, n-1);
    
    taken[n-1] = false;
    generate_subset(words, n-1);
}

void Solution :: update_score(vector<string>& words)
{
    int current_score = 0;
    vector<int> freq(26, 0);
    
    for(int i = 0; i < words.size(); i++)
    {
        if(taken[i])
        {
            for(auto ele : words[i])
            {
                int ind = ele - 'a';
                current_score += score[ind];
                freq[ind]++;
                
                if(freq[ind] > count[ind])
                      return;
            }
        }
    }
                      
    max_sum = max(max_sum, current_score);
}
                      
int Solution :: maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score)
{
    taken.resize(words.size(), false);
    count.resize(26, 0);
    this->score = score;
    
    for(auto ele : letters)
        count[ele - 'a']++;
    
    int n = words.size();
    generate_subset(words, n);
    
    return max_sum;
}