LeetCode 93. Restore IP Addresses

思路

回溯(backtracing)，用s的起始位置pos表示当前的状态（pos之前的已经处理完）。那么就依次尝试1~3位的字符看看是否符合要求，符合就把结果更新到buffer里，未完成就递归继续，然后递归返回的时候记得把buffer恢复到之前的状态。
按照题目的意思，应该不允许IP地址有前导0，即01.01.01.01这种状态.
对了，stoi函数很好用，应该是C++11新加的。

代码

class Solution {
public:
    bool isValidSubAddr(const string& s, int pos, int len){
        if(pos + len > s.size())
            return false;
        int val = stoi(s.substr(pos, len));
        if(val >= 0 && val <= 255){
            if(val < 10 && len > 1)
                return false;
            else if(val < 100 && len > 2)
                return false;
            return true;
        }
        return false;
    }
    void restoreSub(vector<string>& results, const string& s, int pos, int remainingDot, string& buffer){
        if(remainingDot == 0 || pos >= s.size())
            return;
        int buffSize = buffer.size();
        for(int len=1; len<=3; len++){
            if(!isValidSubAddr(s, pos, len))
                continue;
            buffer += s.substr(pos, len);
            if(pos + len == s.size()){
                //one solution
                if(remainingDot == 1) //otherwise, the split cannot be finished
                    results.push_back(buffer);
            } else {
                buffer += ".";
                //continue try
                restoreSub(results, s, pos+len, remainingDot-1, buffer);
            }
            buffer.erase(buffSize); //restore state
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> results;
        if(s.empty()){
            return results;
        }
        string buffer;
        restoreSub(results, s, 0, 4, buffer);
        return results;
    }
};