93.Restore IP Addresses(Recursion)

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        dfs(s, 0, 0);
        return result;
    }
    void dfs(string s, int startPos, int depth)
    {
        if (depth ==3) //IP地址最多4段
        {
            string str = s.substr(startPos,s.length()-startPos);
            int restStrLen = str.length();
            int n = atoi(str.c_str());
            if(n>255) return; //每段8bit，所以最大值是2^8=255
            if(restStrLen > 1 && s[startPos]==‘0‘) return; //每段可以=0，但若!=0，则不能以0开始
            result.push_back(s);
        }
        else
        {       
            string str = s.substr(startPos,s.length()-startPos);
            int restStrLen = str.length();
            if(restStrLen>=4-depth) //每段至少有一个数字
            {         
                str = s.substr(0,startPos+1)+"."+s.substr(startPos+1,restStrLen-1);
                dfs(str, startPos+2, depth+1); //该段只有1个字符的情况
                if(s[startPos] == ‘0‘) return;
            }
            if(restStrLen>=5-depth)
            {
                str = s.substr(0,startPos+2) +"."+s.substr(startPos+2,restStrLen-2);
                dfs(str, startPos+3, depth+1); //该段有2个字符的情况
            }
            if(restStrLen>=6-depth) //该段有3个字符的情况
            {
                str =  s.substr(startPos,3);
                int n = atoi(str.c_str());
                if(n>255) return;
                str = s.substr(0,startPos+3)+"."+s.substr(startPos+3,restStrLen-3);
                dfs(str, startPos+4, depth+1);
            }
        }
    }
private:
    vector<string> result;
};