питон рекурсии

Question

Update: Я забыл кавычки ... легко исправить ...

Я пытался сделать Leetcode вопрос, вопрос, # 93 восстановления IP-адреса.

Если строка содержит только цифры, восстановите ее, возвращая все допустимые допустимые IP-адреса. .

Например: Дано "25525511135",

возвращение [ "255.255.11.135", "255.255.111.35"]. (Порядок не имеет значения)

Это правильный код с помощью DFS:

class Solution(object): 
    def restoreIpAddresses(self, s): 
     """ 
     :type s: str 
     :rtype: List[str] 
     """ 
     res = [] 
     self.restore(s,0,[],res) 
     return res 
    def restore(self,s,count,path,res): 
     if count == 4: 
      if not s: 
       temp = '.'.join(path) 
       res.append(temp) 
      else: 
       return 
     if not s: 
      return 
     if len(s)>2 and int(s[:3])<256 and int(s[:3])>99: 
      self.restore(s[3:],count+1,path+[s[:3]],res) 
     if len(s)>1 and int(s[:2])>9: 
      self.restore(s[2:],count+1,path+[s[:2]],res) 
     self.restore(s[1:],count+1,path+[s[:1]],res) 
     return res 

Это еще один подход:

class Solution(object): 
    def restoreIpAddresses(self, s): 
     """ 
     :type s: str 
     :rtype: List[str] 
     """ 
     res = [] 
     self.restore(s,0,[],res) 
     return res 
    def restore(self,s,count,path,res): 
     if count == 4: 
      if not s: 
       temp = '.'.join(path) 
       res.append(temp) 
      else: 
       return 
     if not s: 
      return 
     if s[0] == '0': 
      #self.restore(s[1:],count+1,path+[0],res) 
      self.restore(s[1:],count+1,path+['0'],res) 
     else: 
      if len(s)>2 and int(s[:3])<256: 
       self.restore(s[3:],count+1,path+[s[:3]],res) 
      if len(s)>1: 
       self.restore(s[2:],count+1,path+[s[:2]],res) 
      self.restore(s[1:],count+1,path+[s[:1]],res) 
     return res 

Единственное отличие состоит в том, что второй подход, который я во-первых, проверьте, начинается ли s с '0'. Я не понимаю, почему мой второй подход ошибочен. принять s = '0000' в качестве примера, второй подход не будет писать '0.0.0.0' до res даже s == '' и count = 4 Пожалуйста, помогите, спасибо!

Answer 1

Вопрос, вероятно, с этим утверждением:

if s[0] == '0': 
     self.restore(s[1:],count+1,path+[0],res) 

Это полосы ведущие нули. Если вход ничего, кроме нулей, ну, тогда ничего не осталось.