1 題目描述

給定一個(gè)僅包含數(shù)字的字符串，通過返回所有有效的IP地址組合來還原它。

例子：

輸入：

"25525511135"

輸出：

["255.255.11.135", "255.255.111.35"]

題目出處：

https://leetcode.com/problems/restore-ip-addresses/

2 解決思路

采用遞歸算法，require標(biāo)識所需的數(shù)字段。

a）從最左分別取1-3個(gè)滿足0~255的數(shù)字；

b）遞歸處理剩余字符串，且所需的數(shù)字段變?yōu)閞equire-1；

c）若require為1，判斷是否滿足ip段內(nèi)數(shù)字要求，滿足返回，不滿足返回空數(shù)組；

d）將a、b兩步所得結(jié)果拼接為數(shù)組返回。

3 golang實(shí)現(xiàn)代碼

https://github.com/olzhy/leetcode/blob/master/93_Restore_IP_Addresses/test.go

4 問題

以上算法時(shí)間復(fù)雜度多少？有更優(yōu)的方案嗎？歡迎留言討論。

原文：https://leileiluoluo.com/posts/leetcode-restore-ip-addresses.html

本文作者：磊磊落落的博客，原創(chuàng)授權(quán)發(fā)布