93. Restore IP Addresses--back tracking -- 类比39 Combinatio

发布时间：2020-12-14 04:14:40 所属栏目：大数据来源：网络整理

导读：93 给你一串数字，让你求出可能的IP 地址。 Input: "25525511135"Output: ["255.255.11.135","255.255.111.35"] 仔细分析一下这题和39题几乎完全一样呀，39是给你一个没有重复数组，可以重复使用数组里的数字之和来组成 target. Input: candidates = targ

93 给你一串数字，让你求出可能的IP 地址。

Input: "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

仔细分析一下这题和39题 几乎完全一样呀，39是给你 一个没有重复数组，可以重复使用数组里的数字之和来组成 target.

Input: candidates = target =,A solution set is:
[
  [7],[2,2,3]
]

93题本质： 因为IP 地址只能是1~3位， 假设有一个数组 nums = {1,3} 表示每次选择IP地址的长度,然后 从Nums里可以用重复数字，一共取4次，当取得数字的sum = input 字符串的长度 时，说明选择的长度为合法的。
         然后验证该长度下IP 地址是否合法， 以下两种为 非法情况： 1. IP>255  2. IP长度大于1位，但前面有0， 比如 05， 003.

为了便于理解，以及和 39题对照，定义了nums 数组，这段code 只能排 67%,code 如下： [2,3,6,7],7

class Solution {
    public List<String> restoreIpAddresses(String s) {
        
        List<String> result = new ArrayList<>();
        int[] nums = {1,3};
        dfs(new ArrayList<Integer>(),nums,result,0,s);
        return result;
    }
    
    private void dfs(List<Integer> list,int[] nums,List<String> result,int depth,int sum,String s){
        if(depth == 4 && sum == s.length()){
            String ip = gen_ip_address(list,s);
        
            if(!ip.equals("-1")){
                result.add(ip);
                return;
            }
        }
        
        if(depth == 4 ||  sum > s.length()){
            return;
        }
        
        for(int i=0; i< nums.length; i++){
            sum += nums[i];
            list.add(nums[i]);
            dfs(list,depth+1,sum,s);
            sum -= nums[i];
            list.remove(list.size()-1);
        }
    }
    
    private String gen_ip_address(List<Integer> list,String s){
        
        int start = 0;
        String res = "";
        for(int i=0; i<4; i++){
            String si = s.substring(start,start+list.get(i));
            start += list.get(i);
            if(Integer.valueOf(si) >255)
                return "-1";
            if(list.get(i)>1 && si.charAt(0) == ‘0‘)
                return "-1";
            if(i<3) res += si+".";
            else res+= si;
        } 
        return res;
    }
}

去掉了 nums 并且用remain 代替sum,可以排名95%：?

class Solution {
    public List<String> restoreIpAddresses(String s) {
        
        List<String> result = new ArrayList<>();
        dfs(new ArrayList<Integer>(),s.length(),int remain,String s){
        if(depth == 4 && remain == 0){
            String ip = gen_ip_address(list,s);
            if(!ip.equals("-1")){
                result.add(ip);
                return;
            }
        }
        
        if(depth == 4 ||  remain <0){
            return;
        }  
        for(int i=1; i<=3; i++){
            list.add(i);
            dfs(list,depth+1,remain-i,s);
            list.remove(list.size()-1);
        }
    }
    
    private String gen_ip_address(List<Integer> list,String s){  
        int start = 0;
        String res = "";
        for(int i=0; i<4; i++){
            String si = s.substring(start,start+list.get(i));
            start += list.get(i);
            
            if(Integer.valueOf(si) >255)
                return "-1";
            if(list.get(i)>1 && si.charAt(0) == ‘0‘)
                return "-1";
            if(i<3) res += si+".";
            else res+= si;
        } 
        return res;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!