Maximum Score Words Formed by Letters LeetCode solution in C++

1
class Solution {
2
 public:
3
  int calc(vector<string> &words, map<char, int> &m, vector<int> &score, int i) {
4
    int maxi = 0;
5
    if (i == words.size()) return 0;
6
    map<char, int> m1 = m; // Creating a duplicate in case the given word does
7
                           // not satisfy our answer
8
    int c = 0;             // Store the score
9
    for (int j = 0; j < words[i].length(); j++) {
10
      if (m1.find(words[i][j]) == m1.end() ||
11
          m1[words[i][j]] == 0) { // If frequency of the letter reduces to zero or that letter
12
                                  // is not present in our hashMap
13
        c = -1;
14
        break;
15
      }
16
      c += score[words[i][j] - 'a'];
17
      m1[words[i][j]]--;
18
    }
19
    if (c != -1)
20
      maxi = c + (calc(words, m1, score,
21
                       i + 1)); // We are considering the current word and
22
                                // adding it to our answer
23
    return max(maxi, calc(words, m, score,
24
                          i + 1)); // FInding tha maximum between when we consider the
25
                                   // current word and when we DONT consider current word
26
  }
27
  int maxScoreWords(vector<string> &words, vector<char> &letters, vector<int> &score) {
28
    map<char, int> m;
29
    for (auto i : letters) m[i]++;
30
    return calc(words, m, score, 0);
31
  }
32
};