Create Maximum Number LeetCode solution in Python

1
class Solution:
2
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
3
        m = len(nums1)
4
        n = len(nums2)
5
        dp = {}
6

7
        # get the max number string with "length" from index "i" in nums1 and index "j" in nums2
8
        # using number string to easy to compare
9
        def getMaxNumberString(i, j, length):
10
            if length == 0:
11
                return ""
12

13
            # using memoization to optimize for the overlapping subproblems
14
            key = (i, j, length)
15
            if key in dp:
16
                return dp[key]
17

18
            # greedy to find the possible max digit from nums1 and nums2
19
            # 1) bigger digit in the higher position of the number will get bigger number
20
            # 2) at the same time, we need to ensure that we still have enough digits to form a number with "length" digits
21

22
            # try to find the possible max digit from index i in nums1
23
            index1 = None
24
            for ii in range(i, m):
25
                if (m - ii + n - j) < length:
26
                    break
27
                if index1 is None or nums1[index1] < nums1[ii]:
28
                    index1 = ii
29

30
            # try to find the possible max digit from index j in nums2
31
            index2 = None
32
            for jj in range(j, n):
33
                if (m - i + n - jj) < length:
34
                    break
35
                if index2 is None or nums2[index2] < nums2[jj]:
36
                    index2 = jj
37

38
            maxNumberStr = None
39
            if index1 is not None and index2 is not None:
40
                if nums1[index1] > nums2[index2]:
41
                    maxNumberStr = str(nums1[index1]) + getMaxNumberString(
42
                        index1 + 1, j, length - 1
43
                    )
44
                elif nums1[index1] < nums2[index2]:
45
                    maxNumberStr = str(nums2[index2]) + getMaxNumberString(
46
                        i, index2 + 1, length - 1
47
                    )
48
                else:
49
                    # get the same digit from nums1 and nums2, so need to try two cases and get the max one
50
                    maxNumberStr = max(
51
                        str(nums1[index1])
52
                        + getMaxNumberString(index1 + 1, j, length - 1),
53
                        str(nums2[index2])
54
                        + getMaxNumberString(i, index2 + 1, length - 1),
55
                    )
56
            elif index1 is not None:
57
                maxNumberStr = str(nums1[index1]) + getMaxNumberString(
58
                    index1 + 1, j, length - 1
59
                )
60
            elif index2 is not None:
61
                maxNumberStr = str(nums2[index2]) + getMaxNumberString(
62
                    i, index2 + 1, length - 1
63
                )
64

65
            dp[key] = maxNumberStr
66
            return maxNumberStr
67

68
        result_str = getMaxNumberString(0, 0, k)
69

70
        # number string to digit array
71
        result = []
72
        for c in result_str:
73
            result.append(int(c))
74

75
        return result