93. 复原 IP 地址

[Ni-Guvara]

class Solution {
public:
    vector<string> res;
    vector<string> subIp;
    vector<string> restoreIpAddresses(string s) {
        // 预处理
        if(isNotmal(s))
            return{};
        int len = s.size();
        backtracing(s , 0, len);

        return res;
    }

    bool isNotmal(string s)
    {
        int len = s.size();

        for(int i = 0; i < len ; i++)
        {
            if(s[i] < '0' || s[i] > '9')
                return true;
        }

        return false;
    }

    bool isNum(string s)
    {
        if(s[0] == '0' && s.size() > 1)
            return false;
        int num = stoi(s);
        if(num <= 255 && num >= 0)
            return true;
        return false;
    }

    void backtracing(string & s ,int startIndex , int len)
    {
        if(startIndex >= len && subIp.size() == 4)
        {
            string ip = "";
            for(int i = 0;i < subIp.size();i++)
            {
                ip+=subIp[i];
                ip += '.';
            }
            ip.pop_back();
            res.push_back(ip);

            return;
        }

        for(int i = startIndex ; i < len ; i++)
        {
            string str =s.substr(startIndex , i - startIndex + 1); 
            if(isNum(str))
            {
               subIp.push_back(str);
            }else
            {
                break;
            }

            backtracing(s , i + 1 ,len);
            subIp.pop_back();
        }
    }
};

[Ni-Guvara]

太慢了