Minimum White Tiles After Covering With Carpets LeetCode solution in Java

1
class Solution {
2
  Map<String, Integer> cache;
3

4
  public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
5
    cache = new HashMap<>();
6
    return helper(floor, 0, numCarpets, carpetLen);
7
  }
8

9
  public int helper(String floor, int position, int numCarpets, int carpetLen) {
10
    if (position >= floor.length()) {
11
      return 0;
12
    }
13

14
    if (floor.length() - position <= numCarpets * carpetLen) {
15
      return 0;
16
    }
17

18
    String key = position + ", " + numCarpets;
19
    if (cache.containsKey(key)) {
20
      return cache.get(key);
21
    }
22

23
    if (numCarpets == 0) {
24
      int output = floor.charAt(position) - '0' + helper(floor, position + 1, 0, carpetLen);
25

26
      cache.put(key, output);
27
      return output;
28
    }
29

30
    int output =
31
        Math.min(
32
            floor.charAt(position) - '0' + helper(floor, position + 1, numCarpets, carpetLen),
33
            helper(floor, position + carpetLen, numCarpets - 1, carpetLen));
34

35
    cache.put(key, output);
36
    return output;
37
  }
38
}