首页 > 搜索 > DFS搜索 > LeetCode-Restore IP Addresses[DFS]
2014
11-19

LeetCode-Restore IP Addresses[DFS]

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)

标签: Backtracking String
分析

必须要走到底部才能判断解是否合法,深搜。

代码1

// LeetCode, Restore IP Addresses
// 时间复杂度O(n^4),空间复杂度O(n)
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        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 {
    public List<String> restoreIpAddresses(String s) {
        return restoreIpAddresses(s,4);
    }

    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))
                list.add(s);
            return list;
        }
        
        for(int i=1; i<=3; i++){
            if(s.length() >= i){
                String sub = s.substring(0,i);
                if(validIpNumber(sub)){
                    sub += ".";
                    List<String> restList = restoreIpAddresses(s.substring(i), n-1);
                    for(String str:restList)
                        list.add(sub + str);
                }
            }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;
    }