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
24 ms、92%
2回目のコード:再帰も選択できます
24 ms、92%
例:
入力:「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%