【LeetCode】93. Restore IP Addresses 解題報告（Python & C++）

作者： 負雪明燭

id： fuxuemingzhu

個人部落格： http://fuxuemingzhu.cn/

題目描述

題目大意

解題方法

回溯法

日期

題目位址：https://leetcode.com/problems/restore-ip-addresses/description/

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

題目中給了一個僅有數字組成的字元串，要求這個字元串能構成的合法IP組合。

我是按照Tag刷的，當然知道這個題是回溯法了。。其實隻要看到所有的組合，一般都是用回溯。

第一遍逾時，原因是沒有找到合理的剪枝！！這就是回溯法最難的地方：剪枝！

當然了，看出了測試用例是一個特别長的由1組成的字元串，僅僅這一個測試用例逾時，是以我加上了len(s)和12的判斷就ok了。是以有了下面的版本：

代碼如下：

看到了題目中有别的同學的剪枝方法特别好，那就是每次dfs的時候都去檢查一下所有的字元串的長度是不是能滿足在最多4個3位數字組成，果然速度提升了很多：

二刷的時候，使用的C++，同樣需要使用合理的剪枝，送出的時候有一次WA，原因是沒有考慮0開頭的整數是不合法的。代碼如下：

2018 年 6 月 11 日 —— 今天學科三在路上跑的飛快～

2018 年 12 月 22 日 —— 今天冬至