1 題目描述

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

例子：

輸入：

"25525511135"

輸出：

["255.255.11.135", "255.255.111.35"]

題目出處：

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

2 解決思路

采用遞歸算法，require標識所需的數字段。

a）從最左分別取1-3個滿足0~255的數字；

b）遞歸處理剩余字符串，且所需的數字段變為require-1；

c）若require為1，判斷是否滿足ip段內數字要求，滿足返回，不滿足返回空數組；

d）將a、b兩步所得結果拼接為數組返回。

3 golang實現代碼

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

4 問題

以上算法時間復雜度多少？有更優的方案嗎？歡迎留言討論。

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

本文作者：磊磊落落的博客，原創授權發布