248. Strobogrammatic Number III

[moyuanhuang]

https://leetcode.com/problems/strobogrammatic-number-iii/

• 坑1: 全局变量最好加self, e.g. self.result instead of result
• 坑2: trim DFS的方法: 对于i，把cur[0:i]跟low[0:i], high[0:i]比较，如果还没到的话就continue.比如

i = 2
cur = ['1', '1', '0', '1', '1']
low = '46200'
# since 11 < 46, we should continue

• 坑3: Python string不能直接当numeric比较，一定要转化成int

>>> '6' > '15'
True
>>> int('6') > int('15')
False

Solution

# 248. Strobogrammatic Number III
# hard

class Solution:
    def strobogrammaticInRange(self, low, high):
        """
        :type low: str
        :type high: str
        :rtype: int
        """
        self_sym = {
            '0': '0',
            '1': '1',
            '8': '8'
        }

        mapping = {
            '0': '0',
            '1': '1',
            '6': '9',
            '8': '8',
            '9': '6'
        }
        
        self.result = 0
        
        def my_toi(char_list):
            return int(''.join(char_list))

        def isValid(number):
            return number >= int(low) and number <= int(high)

        def helper(i, cur):
            if i == pivot:
                if n % 2 == 1:
                    for x in self_sym:
                        cur[i] = x
                        if isValid(my_toi(cur)):
                            self.result += 1
                else:
                    if isValid(my_toi(cur)):
                        self.result += 1
                return
            
            for x in mapping:
                if x == '0' and i == 0:
                    continue

                cur[i], cur[n - i - 1] = x, mapping[x]
                # trim search space
                if (n == len(low) and my_toi(cur[:i + 1]) < int(low[:i + 1])) or \
                    (n == len(high) and my_toi(cur[:i + 1]) > int(high[:i + 1])):
                    continue
                
                helper(i + 1, cur[:])


        for n in range(len(low), len(high) + 1):
            pivot = n // 2
            cur = ['0'] * n
            helper(0, cur)

        return self.result