leetCode.93. 复原 IP 地址

题目思路：

代码

// 前导零的判断方法：如果第一个数是0，且第二个数还有数据，那就是前导0，要排除的
// 注意跟单个 0 区分开
class Solution {
public:vector<string> res;vector<string> restoreIpAddresses(string s) {dfs( s, 0, 0, "" );return res;}// u = 遍历到第几个字符了， k = 遍历到第几个整数了，（我们要的只是四个整数）void dfs( string & s, int u, int k, string path ) {if ( s.size() == u ) {if ( k == 4) {// 去掉path最后面的.path.pop_back();res.push_back(path);}return;}// 特判一下，s 这个字符串给出的长度 远超过 12位，我们应该舍去// 标签的ip地址的上限位数是12位 ,k = 4的情况下，s.size() > 12，那就进行舍去接下来的遍历if ( k == 4) return;// t是记录当前的数据大小for ( int i = u, t = 0; i < s.size(); ++ i ) {if ( i > u && s[u] == '0') break; // 前导0t = t * 10 + s[i] - '0';if (t >= 0 && t <= 255) dfs( s, i + 1, k + 1, path + to_string(t) + '.');else break;}}
};