這題的官方難度是Medium，點(diǎn)贊1296，反對505，通過率35.4%。從各項(xiàng)指標(biāo)來說看起來有些中規(guī)中矩，實(shí)際上也的確如此。這道題的解法和立意都有些顯得新意不足，但總體來說題目的質(zhì)量還是可以的，值得一做。

題意

給定一個由數(shù)字組成的字符串，我們希望通過這個字符串得到所有有效ip地址的組合。對于一個有效的ip地址而言，它應(yīng)該有4個數(shù)字組成，每一個數(shù)字的范圍在0到255之間。

一個字符串可能可以轉(zhuǎn)化成多個ip地址，我們需要存儲下來所有可以成立的情況。

樣例

Input: '25525511135'Output: ['255.255.11.135', '255.255.111.35']

題解

這道題的題意蠻新穎的，將字符串和ip地址結(jié)合在了一起，但是題目的內(nèi)核說實(shí)話有些老生常談了，都是那種將一個大局面轉(zhuǎn)化成若干個小局面之和的情況。

我們之前做的全排列問題、八皇后問題等等都是這種，拿八皇后問題舉例，看起來是我們要在棋盤上放置皇后。但實(shí)際上我們最終想要的結(jié)果是放置好了八個皇后之后的局面，這個局面是由放置了每一個皇后之后的小局面組合在一起構(gòu)成的。所以本質(zhì)上也可以看成是小局面組裝成大局面的問題。

說了這么多，其實(shí)只為了說明一點(diǎn)，就是遇到這些大局面拆分小局面的問題，我們可以率先考慮搜索算法。搜索算法除了可以理解成在一個搜索空間或者是一棵搜索樹當(dāng)中尋找到解之外，也可以理解成可以用來尋找一些小局面的組合，讓它們組合起來可以構(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當(dāng)中剛好存了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必須小于等于255num = 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ì)三連，給我一點(diǎn)支持吧（關(guān)注、轉(zhuǎn)發(fā)、點(diǎn)贊）。

以上就是python 輸入字符串生成所有有效的IP地址(LeetCode 93號題)的詳細(xì)內(nèi)容，更多關(guān)于python 生成IP地址的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！