Maximum Score Words Formed by Letters LeetCode solution in Java

1
class Solution {
2
  int[] memo;
3

4
  public int maxScoreWords(String[] words, char[] letters, int[] score) {
5
    memo = new int[words.length];
6
    Arrays.fill(memo, -1);
7
    HashMap<Character, Integer> hm = new HashMap<>();
8
    for (char c : letters) {
9
      int t = hm.getOrDefault(c, 0);
10
      t++;
11
      hm.put(c, t);
12
    }
13
    // return dp(words,hm,score,0,0);
14
    int res = dp(words, hm, score, 0, 0);
15
    // for(int i : memo) System.out.println(i);
16
    return res;
17
  }
18

19
  public int dp(
20
      String[] words,
21
      Map<Character, Integer> hm,
22
      int[] score,
23
      int index,
24
      int cs) { // cs-current Score
25
    if (index == words.length) return cs;
26
    if (memo[index] != -1) return memo[index];
27
    HashMap<Character, Integer> temp = new HashMap<>(hm);
28
    int tcs = cs; // tcs = temporory current score
29

30
    for (char c : words[index].toCharArray()) {
31
      int t = temp.getOrDefault(c, 0);
32
      t--;
33
      if (t < 0) {
34
        return dp(words, hm, score, index + 1, cs);
35
        // memo[index] = dp(words,hm,score,index+1,cs);
36
        // return memo[index];
37
      }
38
      tcs += score[c - 'a'];
39
      temp.put(c, t);
40
    }
41
    return Math.max(dp(words, hm, score, index + 1, cs), dp(words, temp, score, index + 1, tcs));
42
    // memo[index] = Math.max(dp(words,hm,score,index+1,cs),dp(words,temp,score,index+1,tcs));
43
    // return memo[index];
44
  }
45
}