1.题目描述

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)

2.解法分析

最开始我自己写了个代码，不小心被我刷网页刷掉了，在discuss上翻了一下，发现这个代码跟我思路一模一样，实现稍微不同，准确说他实现得比我的精致一些，所以贴上来了，这个算法的思路类似于回溯法，就是用一个中间变量一直保存着当前解析到的ip地址，另一个用于接收随时得到的正确的ip。

class Solution {

public:

vector
           
             restoreIpAddresses(string s) {
           

// Start typing your C/C++ solution below

// DO NOT write int main() function

vector
           
             col;
           

string ip;

partitionIP(s, 0, 0, ip, col);

return col;

}

void partitionIP(string s, int startIndex, int partNum,

string resultIp, vector
           
            & col)
           

{

if(s.size() - startIndex > (4-partNum)*3) return;

if(s.size() - startIndex < (4-partNum)) return;

if(startIndex == s.size() && partNum ==4)

{

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

col.push_back(resultIp);

return;

}

int num =0;

for(int i = startIndex; i< startIndex +3; i++)

{

num = num*10 + (s[i]-'0');

if(num<=255)

{

resultIp+=s[i];

partitionIP(s, i+1, partNum+1, resultIp+'.', col);

}

if(num ==0)

{

break;

}

}

}

};