python 輸入字符串生成所有有效的IP地址(LeetCode 93號題)
這題的官方難度是Medium,點贊1296,反對505,通過率35.4%。從各項指標來說看起來有些中規(guī)中矩,實際上也的確如此。這道題的解法和立意都有些顯得新意不足,但總體來說題目的質(zhì)量還是可以的,值得一做。
題意
給定一個由數(shù)字組成的字符串,我們希望通過這個字符串得到所有有效ip地址的組合。對于一個有效的ip地址而言,它應該有4個數(shù)字組成,每一個數(shù)字的范圍在0到255之間。
一個字符串可能可以轉(zhuǎn)化成多個ip地址,我們需要存儲下來所有可以成立的情況。
樣例
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
題解
這道題的題意蠻新穎的,將字符串和ip地址結(jié)合在了一起,但是題目的內(nèi)核說實話有些老生常談了,都是那種將一個大局面轉(zhuǎn)化成若干個小局面之和的情況。
我們之前做的全排列問題、八皇后問題等等都是這種,拿八皇后問題舉例,看起來是我們要在棋盤上放置皇后。但實際上我們最終想要的結(jié)果是放置好了八個皇后之后的局面,這個局面是由放置了每一個皇后之后的小局面組合在一起構(gòu)成的。所以本質(zhì)上也可以看成是小局面組裝成大局面的問題。
說了這么多,其實只為了說明一點,就是遇到這些大局面拆分小局面的問題,我們可以率先考慮搜索算法。搜索算法除了可以理解成在一個搜索空間或者是一棵搜索樹當中尋找到解之外,也可以理解成可以用來尋找一些小局面的組合,讓它們組合起來可以構(gòu)成我們想要的大局面。
套用到這道題上來,很顯然最后我們想要的大局面是合法的IP地址,而構(gòu)成這個大局面的小局面則是構(gòu)成IP地址的每一個數(shù)字。
這些都搞明白了之后,代碼就很好寫了:
class Solution: def restoreIpAddresses(self, s: str) -> List[str]: n = len(s) if n < 4 or n > 12: return [] ret = [] def dfs(cur, ips): # 如果遞歸結(jié)束,并且ips當中剛好存了4個ip # 則生成答案 if cur >= n: if len(ips) == 4: ret.append('.'.join(ips[:])) return # 遍歷下一個ip是幾位 for i in range(cur, min(cur+3, n)): # 如果超過1位但是第一位是0,那么非法 if s[cur] == '0' and i > cur: return # ip必須小于等于255 num = int(s[cur: i+1]) if num > 255: return # 回溯 ips.append(s[cur: i+1]) dfs(i+1, ips) ips.pop() dfs(0, []) return ret
總結(jié)
有些新意但是思路中規(guī)中矩的搜索問題,熟悉dfs和回溯的話不會很難。
今天的文章到這里就結(jié)束了,如果喜歡本文的話,請來一波素質(zhì)三連,給我一點支持吧(關注、轉(zhuǎn)發(fā)、點贊)。
以上就是python 輸入字符串生成所有有效的IP地址(LeetCode 93號題)的詳細內(nèi)容,更多關于python 生成IP地址的資料請關注腳本之家其它相關文章!
相關文章
python with statement 進行文件操作指南
在Python中,with關鍵字是一個替你管理實現(xiàn)上下文協(xié)議對象的好東西。例如:file等。在file的結(jié)束,會自動關閉該文件句柄。而這正是本文所需要的2014-08-08python 找出list中最大或者最小幾個數(shù)的索引方法
今天小編就為大家分享一篇python 找出list中最大或者最小幾個數(shù)的索引方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10Python發(fā)送form-data請求及拼接form-data內(nèi)容的方法
這篇文章主要介紹了Python發(fā)送form-data請求及拼接form-data內(nèi)容的方法,文中采用的是requests的方式發(fā)送multipart/form-data請求,需要的朋友可以參考下2016-03-03Python協(xié)程asyncio模塊的演變及高級用法
網(wǎng)上很多關于Python協(xié)程asyncio模塊的教程都是基于老版Python的, 本文將以對比方式展示新老Python版本下協(xié)程的寫法有什么不同并總結(jié)了asyncio的一些高級用法, 包括如何獲取協(xié)程任務執(zhí)行結(jié)果,gather和wait方法的區(qū)別以及如何給任務添加回調(diào)函數(shù)。2021-05-05