leetcode 93 复原IP地址

原题传送门—>>

题目描述：

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。

示例1：

• 输入：s = “25525511135”
• 输出：[“255.255.11.135”,”255.255.111.35”]

示例2：

• 输入：s = “0000”
• 输出：[“0.0.0.0”]

标准DFS

不过第一次提交没有剪枝，导致超时，记录一下

class Solution {
public:
    vector<string> ans;
    string ans_;
    vector<string> tmp;
    vector<string> restoreIpAddresses(string s) {
        solve(s, 0);
        return ans;
    }
    int solve(string & s, int start)
    {
        if(tmp.size() > 4)//注意这里的剪枝！！！否则当数据过长会超时
            return 0;
        if(start == s.size())
        {
            if(tmp.size() == 4)
            {
                ans_.clear();
                ans_+=tmp[0];
                for(int i = 1;i < 4; ++i)
                {
                    ans_ += ".";
                    ans_+= tmp[i];
                }
                ans.push_back(ans_);
            }
            return 0;
        }
        for(int i = 1; i < 4; ++i)//i为长度
        {
            if((s[start] == '0')&& (i > 1))
            {
                break;
            }
            if(start + i > s.size())
                break;
            string a(s.begin() + start, s.begin() + start + i);
            if((a > "255")&&(i == 3))
                break;
            tmp.push_back(a);
            solve(s, start + i);
            tmp.pop_back();
        }
        return 0;
    }
};