【Restore IP Addresses 】cpp

题目：

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)

代码：

class Solution {

public:

    vector<string> restoreIpAddresses(string s) {

            const int size = s.size();

            vector<string> ret;

            if ( size> || size< ) return ret;

            string tmp;

            int numDot = ;

            Solution::dfs(ret, tmp, s, , size-, numDot);

            return ret;

    }

        static void dfs( vector<string>& ret, string tmp, string& s, int begin, int end, int numDot)

        {

            if ( numDot== )

            {

                if ( Solution::valid(s.substr(begin,end-begin+)) )

                {

                    tmp += s.substr(begin,end-begin+);

                    ret.push_back(tmp);

                }

                return;

            }

            int localEnd = std::min(end, begin+);

            for ( int i=begin; i<=localEnd; ++i )

            {

                if ( Solution::valid(s.substr(begin,i-begin+)) )

                {

                    Solution::dfs(ret, tmp+s.substr(begin, i-begin+)+".", s, i+, end, numDot-);

                }

            }

        }

        static bool valid( string tmp )

        {

            const int len = tmp.size();

            if ( len== || len> || (len> && tmp[]=='')) return false;

            int sum = ;

            for ( int i = ; i<len; ++i ) sum = sum* + tmp[i]-'';

            return sum<=;

        }

};

tips：

这道题的基础算法模板还是dfs，但是自己却纠结了好久没有AC。

先不说这道题，之前刷过palindrome partitioning这道题（求一个字符串可能被分割出来的所有回文集合），第一感觉就是跟回文分割的这道题很像，觉得应该很轻松AC。

但很快陷入思维泥潭：

1. 什么时候dfs到下一层？

2. ‘.’这个字符是什么时候加到后面，用不用退出来，什么时候退出来？

最后参考了下面的blog（http://blog.csdn.net/linhuanmars/article/details/24683699）才恍然大悟。

1. 什么时候要dfs到下一层：

　　a) 需要dfs到下一层的时候呗（对于此题来说，一层就是IP地址中的一段，即两个'.'之间的部分；对于回文分割来说，就是一个回文字串）

　　b) 敢往下dfs是因为本层的结果是合理的（对于此题来说，合理就是意味着在本层begin到i之间的字符串代表的数字是合法的；对于回文分割来说，本层begin到i构成的字符串，是一个回文）

　　c) 细化深搜的剪枝条件（对于此题来说，每个IP子端最多有3位数字，且如果长度超过1不能以0开头；对于回文字子符串来说，至少一个元素肯定是回文，再往后走看能否继续是回文，直到走到不能走）

　　d) 光需要dfs到下一层是不够的，还要看限制条件是否允许dfs到下一层（对于此题来说，IP地址一共有四段，即最多dfs到第四层就必须终结了）

　　e) 由c)可知dfs的终结条件就是dfs到第四层（对于此题就是numDot==0，numDot初始化为3，每进一层就减1）

　　f) 对于d)的终止条件，会不会出现begin>end的情况？不会的。因为dfs一层每次增加一个元素，最多加到begin==end，此时经过valid函数判断是无效的，就什么都不做返回上一层，上一层已经到了begin==end的条件→结束，再返回上一层...

2. 如何处理‘.’这个字符：

　　a) 由于dfs一层代表IP地址的一个段，因此，必须保证进入下一层的时候，tmp的结尾是'.' （想明白这一点比较重要，不会纠结于tmp到底最后一个元素是什么的思维泥潭了）

　　b) '.'还影响到了终止条件，如果tmp中已经有了三个'.'了（即numDot==0）,则下面的已经不需要再分支了，一股脑都加入tmp后面即可（算是一种剪枝策略吧）

完毕~

===================================

第二次过这道题，.011.这种形式的不合法，第一次忘记判断了，后面加入了就AC了。

class Solution {

public:

        vector<string> restoreIpAddresses(string s)

        {

            vector<string> ret;

            if ( s.size()> || s.size()< ) return ret;

            vector<string> tmp;

            Solution::dfs(ret, tmp, s);

            return ret;

        }

        static void dfs(vector<string>& ret, vector<string>& tmp, string s)

        {

            if ( tmp.size()== )

            {

                if ( Solution::isValid(s) )

                {

                    tmp.push_back(s);

                    string str = tmp[] + "." + tmp[] + "." + tmp[] + "." + tmp[];

                    ret.push_back(str);

                    tmp.pop_back();

                    return;

                }

            }

            for ( int i=; i<=min((int)s.size(),); ++i )

            {

                if ( !Solution::isValid(s.substr(,i)) ) continue;

                tmp.push_back(s.substr(,i));

                Solution::dfs(ret, tmp, s.substr(i,s.size()-i+));

                tmp.pop_back();

            }

        }

        static bool isValid(string s)

        {

            int val = ;

            int len = s.size();

            if ( len== || len> || (len> && s[]=='')) return false;

            for ( int i=; i<s.size(); ++i ) val = val* + s[i]-'';

            return val<=;

        }

};

巴特西

【Restore IP Addresses 】cpp

最新文章

热门文章