leetCode.93. 复原 IP 地址

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; // 前导0

            t = t * 10 + s[i] - '0';
            if (t >= 0 && t <= 255) dfs( s, i + 1, k + 1, path + to_string(t) + '.');
            else break;
        }
    }
};