[剑指Offer] Day 10: Dynamic Programming

Authored by Tony Feng

Created on April 21st, 2022

Last Modified on April 21st, 2022

Task 1 - Q48. 最长不含重复字符的子字符串

Question

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
e.g.
输入: “abcabcbb”, 输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dict = {}
        res = tmp = 0
        for j in range(0, len(s)):
            i = dict.get(s[j], -1) # get index i, the position where s[j] exists
            dict[s[j]] = j         # update the hash map
            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
            res = max(res, tmp)    # max(dp[j - 1], dp[j])
        return res

Explanation

tmp records the length of the unrepeated substring ending with s[j].
dict records the last position where each key exists.
Time Complexity: O(N)
Space Complexity: O(1)

Task 2 - Q46. 把数字翻译成字符串

Question

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
e.g.
输入: 12258, 输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution: # dp
    def translateNum(self, num: int) -> int:
        num = list(str(num))
        dp = [1 for _ in range(0, len(num)+1)] # dp[0] == dp[1] == 1

        for i in range(2, len(num)+1):
            # dp[i] means the sum of the approaches before num[i] (i.e., num[0] ... num[i-1])
            # Be careful with the index here
            if int(num[i-2] + num[i-1]) < 26 and int(num[i-2]) != 0: 
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]

        return dp[-1]

Solution 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution: # Recursion
    def translateNum(self, num: int) -> int:
        def recur(arr):
            if len(arr) <= 1: # base case
                return 1

            # no need to count on "01", "02", ..., "09" 
            # no need to count on num >= 26
            if int(arr[0] + arr[1]) < 26 and int(arr[0]) != 0:
                return recur(arr[1:]) + recur(arr[2:])
            else:
                return recur(arr[1:])

        return recur(str(num))

Explanation

Solution 1
- Time Complexity: O(N)
- Space Complexity: O(N)
Solution 2
- Time Complexity: O(2^N)
- Space Complexity: O(N)