复原IP地址

末蓝、 2022-01-21 08:47 316阅读 0赞

## 1.题目描述 ##

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
    输出: ["255.255.11.135", "255.255.111.35"]

## 2.解法 ##

### 2.1 回溯剪枝法 ###

private int n;
    	
    private String s;
    
    private LinkedList<String> segments = new LinkedList<String>();
    
    private List<String> res = new ArrayList<String>();
    
    public List<String> restoreIpAddresses(String s) { 
    	this.s =s;
    	n = s.length();
    	back_track(0, 1);
    	return res;
       }
    
    /** * 回溯剪枝法 * @param prev_pos：上一个已放置的位置 * @param dot：已放置的点的数量 */
    private void back_track(int prev_pos, int dot) { 
    	int next_pos = Math.min(n-1, prev_pos+3);
    	for(int cur_pos=prev_pos+1;cur_pos<=next_pos;cur_pos++) { 
    		String str = s.substring(prev_pos, cur_pos);
    		if(validPot(str)) { 
    			segments.add(str);
    			if(dot ==3) { 
    				handleRes(cur_pos);
    			}else { 
    				back_track(cur_pos, dot+1);
    			}
    			segments.removeLast();
    		}
    	}
    }
    
    private void handleRes(int cur_pos) { 
    	String remainStr = s.substring(cur_pos);
    	if(validPot(remainStr)) { 
    		segments.add(remainStr);
    		res.add(String.join(".", segments));
    		segments.removeLast();
    	}
    }
    
    private boolean validPot(String str) { 
    	if(str == null || str.length()<1 || str.length()>3) { 
    		return false;
    	}
    	return str.charAt(0)=='0'?str.length()==1 : Integer.parseInt(str)<256;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，316人围观）

还没有评论，来说两句吧...

相关阅读

相关 93. 复原 IP 地址

93. 复原 IP 地址有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。例如：“0.1.2

た入场券/ 2024年03月31日 13:39/ 0 赞/ 96 阅读

相关 LeetCode-93. 复原 IP 地址

目录题目思路回溯法题目来源 [93. 复原 IP 地址][93. _ IP] 题目思路意识到这是切割问题，切割问题就可以使

一时失言乱红尘/ 2024年03月26日 04:13/ 0 赞/ 78 阅读

相关 leetcode93 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。示例: 输入: “25525511135” 输出: \[“255.255.11.135”, “25

雨点打透心脏的1/2处/ 2023年06月19日 06:52/ 0 赞/ 126 阅读

相关复原IP地址

一、前言问题来源LeetCode 问题链接：[https://leetcode-cn.com/explore/interview/card/bytedance/242

谁践踏了优雅/ 2023年02月18日 03:23/ 0 赞/ 130 阅读

相关 LeetCode 93. 复原 IP 地址

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

比眉伴天荒/ 2022年11月04日 13:29/ 0 赞/ 177 阅读

相关 leetcode93复原ip地址

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

傷城~/ 2022年10月14日 00:54/ 0 赞/ 169 阅读

相关 Leetcode 93. 复原 IP 地址

题目重述给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。你可以按任何顺序返回答案。有效 IP 地址正好由四个

迷南。/ 2022年09月02日 11:55/ 0 赞/ 167 阅读

相关 leetcode 93 复原IP地址

前言题目：[93. 复原 IP 地址][93. _ IP] 参考题解：[复原 IP 地址-代码随想录][IP _-] --------------------

蔚落/ 2022年08月28日 11:51/ 0 赞/ 176 阅读

相关 [LeetCode] Restore IP Addresses 复原IP地址

Given a string containing only digits, restore it by returning all possible valid IP add

红太狼/ 2022年04月14日 01:29/ 0 赞/ 187 阅读

相关复原IP地址

1.题目描述给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。示例: 输入: "25525511135" 输出: ["255.2

末蓝、/ 2022年01月21日 08:47/ 0 赞/ 317 阅读