2014
11-19

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)

// LeetCode, Restore IP Addresses
// 时间复杂度O(n^4)，空间复杂度O(n)
class Solution {
public:
vector<string> result;
string ip; // 存放中间结果
dfs(s, 0, 0, ip, result);
return result;
}

/**
* @brief 解析字符串
* @param[in] s 字符串，输入数据
* @param[in] startIndex 从s的哪里开始
* @param[in] step 当前步骤编号，从0开始编号，取值为0,1,2,3,4表示结束了
* @param[out] intermediate 当前解析出来的中间结果
* @param[out] result 存放所有可能的IP地址
* @return 无
*/
void dfs(string s, size_t start, size_t step, string ip,
vector<string> &result) {
if (start == s.size() && step == 4) {  // 找到一个合法解
ip.resize(ip.size() - 1);
result.push_back(ip);
return;
}

if (s.size() - start > (4 - step) * 3)
return;  // 剪枝
if (s.size() - start < (4 - step))
return;  // 剪枝

int num = 0;
for (size_t i = start; i < start + 3; i++) {
num = num * 10 + (s[i] - '0');

if (num <= 255) {  // 当前结点合法，则继续往下递归
ip += s[i];
dfs(s, i + 1, step + 1, ip + '.', result);
}
if (num == 0) break;  // 不允许前缀0，但允许单个0
}
}
};


Java代码:

public class Solution {
}

private boolean validIpNumber(String s){
return  Integer.parseInt(s) - 256 < 0 && !(s.charAt(0) == '0' && s.length() > 1);
}

//restore Ip Addresses in n parts
public List<String> restoreIpAddresses(String s,int n) {
List<String> list = new ArrayList<String>();

//valid string
if(s.length()/n > 3 || (s.length()/n == 3 && s.length()%n != 0) || s.length() < n)
return list;

//base case, return
if(n == 1 ){
if(validIpNumber(s))
return list;
}

for(int i=1; i<=3; i++){
if(s.length() >= i){
String sub = s.substring(0,i);
if(validIpNumber(sub)){
sub += ".";
for(String str:restList)
}
}else{
break;
}
}
return list;
}
}

1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}