leetcode 93: restore IP address

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)

这个题目是很典型的dfs的题目，但是很不容易写对，对于dfs的剪枝条件比较多，而且相对比较复杂。

剪枝条件1： 在每一层进行之前，需要先对s里面剩下没有处理的字符串字符个数进行判断， 剩下的字符个数需要在最长可能个数和最短可能个数之间， 最长可能个数：（4-cur）*3 , 即剩下每一层都有3个字符， 最短可能个数， 4-cur， 即剩下每一层只有一个字符， 在这两种情况之外的情况都需要return， 获得一个可用结果的条件是，cur到了最后那层，并且string 遍历完毕。

2. 对于在每一层进行计算过程中， 要注意： 00，  05， ....这些情况是不合理的，即如果求得的字符串的int数为0， 那么就直接return，而不继续往后dfs了。 

这个题目感觉属于dfs里面剪枝比较复杂的题目了。注意剪枝判断。

class Solution {

private:

    void dfs(string &s, vector<string> &rst, string solu, int cur, int index) {

        //(4-cur)* 3 is the longest remaining substring

        if (s.size() - index  > (4-cur) * 3) {

            return;

        }

        //4-cur is the minimal remaining substring

        if (s.size() - index < (4-cur)) {

            return;

        }

        if (index == s.size() && cur == 4) {

            solu.resize(solu.size()-1);

            rst.push_back(solu);

            return;

        }

        for (int i = 1; i <= 3; i++) {

            string tmp = s.substr(index, i);

            string buf = solu;

            solu += tmp + '.';

            int itmp = stoi(tmp);

            if (itmp<= 255 && itmp >= 0) {

                dfs(s, rst, solu, cur+1, index+i);

            }

            solu = buf;

          if (itmp == 0) break;  

        }

    }

public:

    vector<string> restoreIpAddresses(string s) {

        vector<string> rst;

        if (s.size() == 0) return rst;

        dfs(s, rst, "", 0, 0);

        return rst;

    }

};