[LeetCode]93.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)

思路

基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成），每个数都必须小于等于255。并且这里树的层数不会超过四层，因为IP地址由四段组成，到了之后我们就没必要再递归下去，可以结束了。

代码

/*---------------------------------------
*   日期：2015-05-15
*   作者：SJF0115
*   题目: 93.Restore IP Addresses
*   网址：https://leetcode.com/problems/restore-ip-addresses/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        int size = s.size();
        if(size == 0){
            return result;
        }//if
        string ip;
        helper(s,1,0,ip,result);
        return result;
    }
private:
    int to_int(string str){
        int size = str.size();
        if(size == 0){
            return 0;
        }//if
        int result = 0;
        for(int i = 0;i < size;++i){
            result = result * 10 + str[i] - '0';
        }//for
        return result;
    }
    void helper(string &str,int step,int index,string ip,vector<string> &result){
        // 终止条件
        int size = str.size();
        if(step == 5){
            if(index == size){
                result.push_back(ip);
            }//if
            return;
        }//if
        string part;
        for(int i = 1;i <= 3;++i){
            // 不能以0开始(单个0可以)
            if(i != 1 && str[index] == '0'){
                break;
            }//if
            if(index+i <= size){
                part = str.substr(index,i);
                if(to_int(part) <= 255){
                    string tmp = ip;
                    if(step != 1){
                        tmp += ".";
                    }//if
                    tmp += part;
                    helper(str,step+1,index+i,tmp,result);
                }//if
            }//if
        }//for
    }
};

int main(){
    Solution s;
    //string str("25525511135");
    string str("010010");
    vector<string> vec = s.restoreIpAddresses(str);
    for(int i = 0;i < vec.size();++i){
        cout<<vec[i]<<endl;
    }//for
    return 0;
}

运行时间