Solution to JZ 46 Translate numbers to letters & JZ 47 Max price of gift.
JZ 46
Translate numbers to letters (Medium). [link]
If two digits can be translated together, the number ended with digit i has f(i-2) numbers of translation. If translate one digit only, the number ended with digit i has f(i-1) numbers of translation. Therefore, the function is as follows:
# Pseudocode
if x[i-1, i+1]: # two digits can be translated together
dp[i] = f(i-1) + f(i-2)
else:
dp[i] = f(i-1)
To reduce the space complexity, we use a rolling array to store f(i-1) and f(i-2), since f(i) depends only on f(i-1) and f(i-2). Note that we have to consider ‘01’, ‘02’ …. which cannot translate to letters.
Time complexity O(n), space complexity O(n).
class Solution:
def solve(self, nums: str):
if nums[0] == '0':
return 0
a = b = 1
for i in range(1, len(nums)):
tmp = b if nums[i] != '0' else 0
if 9 < int(nums[i-1:i+1]) <= 26:
tmp += a
a, b = b, tmp
return b
JZ 47
Max price of gift (Medium). [link]
The DP function for price is f[i,j] = max(f[i, j-1] + f[i-1, j])+ grid[i,j] . We can create and update a new matrix dp (space complexity O(MN)) or update the given grid to save space (space complexity O(1)). The time complexity is O(MN).
class Solution:
def maxValue(self , grid: List[List[int]]) -> int:
for i in range(len(grid)):
for j in range(len(grid[0])):
if i == 0 and j == 0: continue
if i == 0: grid[i][j] += grid[i][j-1]
elif j == 0: grid[i][j] += grid[i-1][j]
else: grid[i][j] += max(grid[i][j-1], grid[i-1][j])
return grid[-1][-1]
To be more efficient, we can deal with the first row and first column first.
class Solution:
def maxValue(self , grid: List[List[int]]) -> int:
for i in range(1, len(grid[0])):
grid[0][i] += grid[0][i-1]
for i in range(1, len(grid)):
grid[i][0] += grid[i-1][0]
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
grid[i][j] += max(grid[i][j-1], grid[i-1][j])
return grid[-1][-1]
