Form Largest Integer With Digits That Add up to Target LeetCode solution in Java

1
// Space Complexity = O(N*M) (N == length of cost array and M == target )
2
// Time Complexity = O(N*M)
3

4
class Solution {
5
  Map<String, String> map = new HashMap<>();
6
  String[][] memo;
7

8
  public String largestNumber(int[] cost, int target) {
9
    memo = new String[cost.length + 1][target + 1];
10

11
    for (int i = 0; i <= cost.length; i++) {
12
      for (int j = 0; j <= target; j++) memo[i][j] = "0";
13
    }
14

15
    String res = helper(cost, cost.length - 1, target);
16

17
    return res == "-1" ? "0" : res;
18
  }
19

20
  public String helper(int[] cost, int index, int target) {
21
    if (target == 0) {
22
      return "";
23
    }
24

25
    if (target < 0) return "-1";
26

27
    if (index < 0) return "-1";
28

29
    if (memo[index][target] != "0") return memo[index][target];
30

31
    String str1 = (index + 1) + helper(cost, cost.length - 1, target - cost[index]);
32
    String str2 = helper(cost, index - 1, target);
33

34
    String res = getBigger(str1, str2);
35

36
    memo[index][target] = res;
37

38
    return res;
39
  }
40

41
  public String getBigger(String num1, String num2) {
42
    if (num1.contains("-1")) return num2;
43
    if (num2.contains("-1")) return num1;
44
    if (num1.length() > num2.length()) return num1;
45
    if (num2.length() > num1.length()) return num2;
46
    return Double.parseDouble(num1) < Double.parseDouble(num2) ? num2 : num1;
47
  }
48
}