LeetCode #93：Restore IP Addresses(复原IP地址)

题目描述

本题仍然是使用回溯法来进行解决的问题。与之前问题不同的是本题基于字符串进行回溯，需要使用一系列操作字符串的函数，在做题时因为对这些函数的用法不熟悉走了一些弯路，特此记录。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        this->n = s.length();

        if(n < 4 || n > 12) // IP地址最低4位、最高12位十进制数
            return res;

        dfs(0, s);

        return res;
    }

    vector<string> res;
    vector<string> temp; // 临时存放IP的四个段
    int n;

    void dfs(int depth, string s) {
        if(depth == 4 && s.length() == 0) {
            res.push_back(temp[0] + '.' + temp[1] + '.' + temp[2] + '.' + temp[3]);
            return;
        } 
        
        if(depth == 4 && s.length() != 0) { // 生成四个段后s还没有用完，剪枝
            return;
        }

        for(int i = 1; i <= 3 && i <= s.length(); i ++) { // i <= s.length() 是为了防止越右边界，可能导致check函数中的stoi因为传入空串无法工作
            string num = s.substr(0, i); // substr函数取的是第一个参数pos往后数I个元素的子串（包括pos）
            if(check(num)) {
                temp.push_back(num);
                dfs(depth + 1, s.substr(i)); // 若不写第二个参数，默认截取到字符串末尾
                temp.pop_back();
            }     
        }
    }

    bool check(string num) { // 检验IP段是否合法
        if(num.size() > 1 && num[0] == '0') // 检测前导0
            return false;

        return stoi(num) <= 255; // 每个部分均小于等于255，stoi为字符串转整数的标准库函数
    }

};