Skip to content

1255. Maximum Score Words Formed by Letters 👍

  • Time: $O(|\texttt{letters}| + 2^{|\texttt{words}|})$
  • Space: $O(|\texttt{letters}| + 2^{|\texttt{words}|})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
 public:
  int maxScoreWords(vector<string>& words, vector<char>& letters,
                    vector<int>& score) {
    vector<int> count(26);
    for (const char c : letters)
      ++count[c - 'a'];
    return dfs(words, 0, count, score);
  }

 private:
  // Returns the maximum score you can get from words[s..n).
  int dfs(const vector<string>& words, int s, vector<int>& count,
          const vector<int>& score) {
    int ans = 0;
    for (int i = s; i < words.size(); ++i) {
      const int earned = useWord(words, i, count, score);
      if (earned > 0)
        ans = max(ans, earned + dfs(words, i + 1, count, score));
      unuseWord(words, i, count);
    }
    return ans;
  }

  int useWord(const vector<string>& words, int i, vector<int>& count,
              const vector<int>& score) {
    bool isValid = true;
    int earned = 0;
    for (const char c : words[i]) {
      if (--count[c - 'a'] < 0)
        isValid = false;
      earned += score[c - 'a'];
    }
    return isValid ? earned : -1;
  }

  void unuseWord(const vector<string>& words, int i, vector<int>& count) {
    for (const char c : words[i])
      ++count[c - 'a'];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int maxScoreWords(String[] words, char[] letters, int[] score) {
    int[] count = new int[26];
    for (final char c : letters)
      ++count[c - 'a'];
    return dfs(words, 0, count, score);
  }

  // Returns the maximum score you can get from words[s..n).
  private int dfs(String[] words, int s, int[] count, int[] score) {
    int ans = 0;
    for (int i = s; i < words.length; ++i) {
      final int earned = useWord(words, i, count, score);
      if (earned > 0)
        ans = Math.max(ans, earned + dfs(words, i + 1, count, score));
      unuseWord(words, i, count);
    }
    return ans;
  }

  int useWord(String[] words, int i, int[] count, int[] score) {
    boolean isValid = true;
    int earned = 0;
    for (final char c : words[i].toCharArray()) {
      if (--count[c - 'a'] < 0)
        isValid = false;
      earned += score[c - 'a'];
    }
    return isValid ? earned : -1;
  }

  void unuseWord(String[] words, int i, int[] count) {
    for (final char c : words[i].toCharArray())
      ++count[c - 'a'];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
  def maxScoreWords(
      self,
      words: list[str],
      letters: list[str],
      score: list[int],
  ) -> int:
    count = collections.Counter(letters)

    def useWord(i: int) -> int:
      isValid = True
      earned = 0
      for c in words[i]:
        count[c] -= 1
        if count[c] < 0:
          isValid = False
        earned += score[string.ascii_lowercase.index(c)]
      return earned if isValid else -1

    def unuseWord(i: int) -> None:
      for c in words[i]:
        count[c] += 1

    def dfs(s: int) -> int:
      """Returns the maximum score you can get from words[s..n)."""
      ans = 0
      for i in range(s, len(words)):
        earned = useWord(i)
        if earned > 0:
          ans = max(ans, earned + dfs(i + 1))
        unuseWord(i)
      return ans

    return dfs(0)