Leetcode笔记（4）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)

这一题思路并不复杂，但是实际做起来有颇多细节需要注意。从思路上看也是动态规划和递归之间trade-off的一个好例子。

首先需要理清题目的基本假设。这一题目本身的表达不够清晰，没有给出各种边界条件的例子。如：是否所有的digit都必须出现在最后的combination中，combination里能不能出现以0起始的两位或三位数。实际上，这一题要求所有digit必须出现，首位不能为0。用一个我的错误输出可以表明：

Input:	"010010"
Output:	["0.1.0.10","0.1.0.10","0.10.0.10","1.0.0.10","0.1.1.0","0.10.1.0","1.0.1.0","0.100.1.0","1.0.1.0","10.0.1.0"]
Expected:	["0.10.0.10","0.100.1.0"]

于是，我们可以对一个字符串判断是否在0~255的范围且符合以上要求：

    bool isValid(const string & s)
    {
        if (s.length() > 3 || s.length() > 1 && s[0] == '0') 
            return false;

        int tmp = std::stoi(s);
        return tmp < 256;
    }

理清这一点后，我的思路直接到了动态规划，从左到右走一遍，在每次最多考虑三位的情况下，效率O(n)。用一个4 * length()的二维数组表示，A[i][j]表示在第j位的完成ip地址i个部分的字符串组合。

class Solution {
public:
    bool isValid(const string & s, int l, int r)
    {
        if (r - l > 2 || (r - l > 0 && s[l] == '0') )
            return false;

        int tmp = std::stoi(s.substr(l, r-l+1));
        return tmp < 256;
    }

    vector<string> restoreIpAddresses(string s) {
        vector<string> tmp;
        if (s.size() < 4 || s.size() > 12)
            return tmp;

        vector<vector<vector<string> > > a(5, vector<vector<string> >(s.size() + 1, vector<string>()));
        a[0][0].push_back("");
        for (int i=1; i<5; i++)
        {
            for (int j = i; j < s.size() + 1; j++)
            {
                vector<string> & cur = a[i][j];
                for (int k = i - 1; k < j; k++)
                {
                    if (!isValid(s, k, j - 1))
                        continue;

                    vector<string> & prev = a[i-1][k];
                    for (int l = 0; l < prev.size(); l++)
                    {
                        stringstream ss;
                        if (!prev[l].empty())
                            ss<<prev[l]<<".";
                        ss<<s.substr(k, j - k);
                        cur.push_back(ss.str());
                    }
                }
            }
        }
        return a[4][s.size()];
    }
};

然而，这一题更常见的方法是直接递归判断。从第0位开始，分别选1位，2位和3位字符串，如果valid的话则从字符串中剩下部分寻找其他部分。由于IP地址总共由四个部分组成，递归的层数最多为4~5层（取决于实际实现）。递归方法代码如下：

class Solution {
public:
    bool isValid(const string & s)
    {
        if (s.length() > 3 || s.length() > 1 && s[0] == '0') 
            return false;

        int tmp = std::stoi(s);
        return tmp < 256;
    }

    void getRes(const string & s, int curPos, int toFind, string curRes, vector<string> & res)
    {
        if (toFind <= 0)
        {
            if (curPos >= s.length())
                res.push_back(curRes);
            return;
        }
        if(curPos >= s.length())
            return;

        for (int i=1; i<= min(3, int(s.length()) - curPos); i++)
        {
            string sub = s.substr(curPos, i);
            if (isValid(sub))
            {
                stringstream ss;
                if (!curRes.empty())
                    ss<<curRes<<".";
                ss<<sub;
                getRes(s, curPos + i, toFind - 1, ss.str(), res);    
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        getRes(s, 0, 4, "", res);
        return res;
    }
};

由于递归层数小+空间复杂度低+减枝发生很早，递归代码的运行时间反而比以上的动态规划更短。

经验总结：

• 动态规划可以解决的问题具有最优子结构的性质，也必定是可以递归解决的。在问题本身不太复杂的时候，递归解法更简洁直观。
• 这一题还有更简单粗暴的解法：使用i,j,k分别标记三个点所在的位置，三层循环嵌套最里判断各部分是否valid
• 经验是好事，但是容易产生stereotype
• 边界值，size()和index的关系要多加小心