Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

tag: backtracking, string

花了我好久才搞通这题！

其实大方向是对的，带剪枝的回溯算法。先一个个插dot进去，发现不行后再返回上一层，逐个测试。

有三个点需要注意：

1. 传参数时，result是要随时被更改的，所以传参时要传它的引用。即使我是调用它的push_back()函数，也需要传引用，这个好奇怪。

2. substr的参数是(index, count)表示取[index, index + cout)的子字符串。开始我以为是[start, end)。结果改了好久，在本地上cout才测试出来。

3. stoi不能转换过长的字符串，否则会报RUN TIME ERROR 错误。所以我在stoi函数前，加了s.size() > 3 的判断。保证传给stoi的字符串不会过长，导致溢出。

4. IP每个域之间必须是一个小于等于255的有效非负整数。像是010这样就不合法，需要加以判定。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> re;
        _restoreIpAddresses(re, s, 0);
        return re;
    }
    //depth: number of dot inserted, it can not be 3
    void _restoreIpAddresses(vector<string> &result, string s, int depth){
        if(depth == 3){//leaf node
            int pos = s.find_last_of('.') + 1;
            string lastPart = s.substr(pos);
            if (lastPart.size() > 3 || lastPart.empty()){
                return;
            }
            if(stoi(lastPart) <= 255){
                if (lastPart[0] == '0' && lastPart.size() > 1){
                    return ;//string starts with '0' but is not '0'
                }
                else{
                    result.push_back(s);
                }
            }
        }
        else{
            int pos = s.find_last_of('.') + 1;
            for(int i = pos; i < pos + 3 && i < s.size(); i++){
                if(s[pos] == '0' && i > pos){//string starts with '0' but is not '0'
                    return;
                }
                if(stoi(s.substr(pos, i -pos + 1)) <= 255){
                    s.insert(i + 1, ".");
                    _restoreIpAddresses(result, s, depth + 1);
                    s.erase(i + 1, 1);
                }
            }    
        }
    }
};