Lintcode426 Restore IP Addresses

【题目描述】

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

给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。

【题目链接】

www.lintcode.com/en/problem/restore-ip-addresses/

【题目解析】

一个有效的IP地址由4个数字组成，每个数字在0-255之间。对于其中的2位数或3位数，不能以0开头。所以对于以s[i]开头的数字有3种可能：

1. s[i]

2. s[i : i+1]，s[i] !=0时

3. s[i : i+2]，s[i] != 0，且s[i : i+2] <= 255

根据以上规律，对s从头开始进行DFS寻找4个数字即可。

【参考答案】

www.jiuzhang.com/solutions/restore-ip-addresses/