Leetcode作題日記:93.IPアドレスの復元(PYTHON)

8963 ワード

数値のみを含む文字列を指定し、それを復元し、可能なすべてのIPアドレスフォーマットを返します.
例:
入力:「2552511135」出力:[「255.255.1.135」、「255.255.11.35」
最初のコード:正しいipアドレスフォーマットとは、X.X.X.X,4セグメントであり、各セグメントは255未満であるが、勝手に分けることはできない.後のXが255より大きい可能性があるからだ.遡及すると、1~3文字ずつ取り、255未満と判断すると再帰し続け、終了後、pop()は次の数字に置き換え、3つの数字が終わるまで、0に遭遇すると1回しか現れないため、私たちは1回だけ再帰するbreak
	def res(s,k,ans,ANS):
            if len(ans)==4 :#    4    ,  4       
                if  k==len(s):
                    ANS.append('.'.join(ans))#         
                return
            else:
                for i in range(k+1,min(k+4,len(s)+1)): #         ,i 
                		#   len(S), [ k   : len(s)   ]
                    if s[k]=='0' and i>k+1: #  0       
                        break
                    a=s[k:i]
                    if int(a) <=255:
                        ans.append(a)
                        res(s,i,ans,ANS)
                        ans.pop() #        
        ans=[]
        res(s,0,[],ans)                
        return ans

24 ms、92%
2回目のコード:再帰も選択できます
	def res(s,ans,k,ANS):
            if k==4: #    4    ,  4       
                if s=='': # s   4 ,  
                    ANS.append('.'.join(ans))
                return
            for i in range(1,min(4,len(s)+1)):#  len(s)+1, i    len(s)
                if int(s[:i])>255 or (s[0]=='0' and i>1):
                    break
                res(s[i:],ans+[s[:i]],k+1,ANS)#     s  ,        
        ans=[]
        res(s,[],0,ans)
        return ans

24 ms、92%