[AC] PYTHON DFS (20 lines)

  • 0

    MY first contribution to this site:
    Key idea:

    1. DFS.
    2. The simplest way is to use TWO numbers to find a summed number in the rest of string.
    3. To get the first TWO numbers, need to have O(n^2) loops.
    class Solution(object):
        def isAdditiveNumber(self, num):
            :type num: str
            :rtype: bool
            def dfs(start, prev_num1, prev_num2): 
                if start == n:   # count !
                    return True
                if prev_num1[0] == "0"and len(prev_num1) > 1: return False
                if prev_num2[0] == "0"and len(prev_num2) > 1: return False
                for i in range(start+1, n+1):   # count to include n
                    if num[start] == "0": continue
                    if int(num[start:i])  == int(prev_num1) + int(prev_num2):
                             if dfs(i, prev_num2, num[start:i]):
                                 return True
                return False
            n = len(num)
            # another key: define first two numbers!
            for i in range(1, n):
                for j in range(i+1, n):
                    if dfs(j, num[:i], num[i:j]):
                        return True
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.