Beats 100.00% of python submissions surprisingly!
It's a tough way to solve this problem.\n\nMy solution is trying to construct the answer.\n\n1. At first, using dp[i][j][k] as a set to record the state, which 
It's a tough way to solve this problem.\n\nMy solution is trying to construct the answer.\n\n1. At first, using dp[i][j][k] as a set to record the state, which means the k-length result from arr1[i:] and arr[j:]. But got TLE.\n2. After that, trying to pre-process loc[i][x] to locate the digit x in arr[i:]. But still TLE.\n3. Finally, handling the case when l1+l2 == k. Got AC.\n\nI think the complexity maybe O((m+n+k)*10), since the number of answer is k*10.\n\nHere is my code. 128ms in py.\n\n    ### 321. Create Maximum Number ###\n    # @param {integer[]} nums1\n    # @param {integer[]} nums2\n    # @param {integer} k\n    # @return {integer[]}\n    def maxNumber(self, nums1, nums2, k):\n        if not k or len(nums1)+len(nums2)<k: return []\n    \n        loc1 = [[-1]*10 for _ in range(len(nums1)+1)]\n        loc2 = [[-1]*10 for _ in range(len(nums2)+1)]\n        l12 = len(nums1)+len(nums2)\n        vis, res = set(), [-1]*k\n    \n        def make(nums, loc):\n            pos = [-1]*10\n            for i in xrange(len(nums)-1,-1,-1):\n                pos[nums[i]] = i\n                for j in range(10):\n                    loc[i][j] = pos[j]\n    \n        make(nums1, loc1)\n        make(nums2, loc2)\n    \n        def compare(p1, p2):\n            if p2 == len(nums2): return 1\n            if p1 == len(nums1): return 2\n            if nums1[p1] > nums2[p2]: return 1\n            if nums1[p1] < nums2[p2]: return 2\n            return compare(p1+1, p2+1)\n    \n        def dfs(p1, p2, k):\n            if k == 0 or (p1, p2, k) in vis: return\n    \n            if l12 == p1+p2+k:\n                flag, update = True, False\n                while flag and k>0:\n                    if compare(p1, p2) == 1:\n                        if res[-k] <= nums1[p1] or update:\n                            if res[-k] < nums1[p1]: update = True\n                            res[-k] = nums1[p1]\n                            p1 += 1\n                        else: flag = False\n                    else:\n                        if res[-k] <= nums2[p2] or update:\n                            if res[-k] < nums2[p2]: update = True\n                            res[-k] = nums2[p2]\n                            p2 += 1\n                        else: flag = False\n                    k -= 1\n            else:\n                flag = False\n                for i in range(9,-1,-1):\n                    if loc1[p1][i] != -1:\n                        if l12-loc1[p1][i]-p2 >= k and res[-k] <= i:\n                            if res[-k] < i: res[-k:] = [-1]*k\n                            res[-k] = i\n                            dfs(loc1[p1][i]+1, p2, k-1)\n                            flag = True\n                    if loc2[p2][i] != -1:\n                        if l12-p1-loc2[p2][i] >= k and res[-k] <= i:\n                            if res[-k] < i: res[-k:] = [-1]*k\n                            res[-k] = i\n                            dfs(p1, loc2[p2][i]+1, k-1)\n                            flag = True\n                    if flag: break\n            vis.add((p1, p2, k))\n    \n        dfs(0, 0, k)\n        return res
['Python']