题解 | #数字字符串转化成IP地址#

class Solution {
    vector<string> ans;
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        dfs(s, 0, 0, "");
        return ans;
    }
	// u是搜索的字符串的位置，k是已经划分的数字个数
    void dfs(string& s, int u, int k, string path) {
        if (u == s.size()) {
            if (k == 4) { // 当正好搜索完字符串并且数字个数为4时
                path.pop_back(); // 把末尾的‘.’去掉
                ans.push_back(path);
            }
        }
        if (k == 4) return; // 剪枝
        for (int i = u, t = 0; i < s.size(); i++) {
		  	// 如果搜索的第一位是0，则只允许当作0看待，其他情况当作前导0直接break
            if (i > u && s[u] == '0') {
                break;
            }
            t = t * 10 + s[i] - '0';
            if (t <= 255)
                dfs(s, i + 1, k + 1, path + s.substr(u, i - u + 1) + '.');
        }
    }
};

• 思路：暴搜
• 1、暴搜划分数字的方法
• 2、当当正好搜索完字符串并且数字个数为4时，加入结果中
• 3、注意前导0问题
• 4、只有当数字在0~255范围内才有效
• 时间复杂度：O(C(3, n - 1))
• 空间复杂度：O(不好说)