本文主要是介绍leetcode：Restore IP Addresses 【Java】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、问题描述
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)
二、问题分析
1、采用递归算法；
2、详见代码注释。
三、算法代码
public class Solution {public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<String>();backtrack(result, s, 0, 0, new StringBuffer());//去掉result中每个结果最后的.，例如[255.255.11.135., 255.255.111.35.]for(int i = 0; i < result.size(); i++){result.set(i, result.get(i).substring(0, result.get(i).length() - 1)); }return result;}public void backtrack(List<String> result, String ip, int start, int step, StringBuffer ipBuffer){//find a resolutionif(start == ip.length() && step == 4){result.add(ipBuffer.toString());return;}//IP地址由四段构成，剩余字符串长度大于所有还未生成的IP段的最大有效长度的总和//例如，剩余字符串长度为9，已生成的IP段为255.255，还有最后2段未生成，但9>2*3if((ip.length() - start) > (4 - step) * 3){return;}//IP地址由四段构成，剩余字符串长度小于所有还未生成的IP段的最小有效长度的总和if((ip.length() - start) < (4 - step)){return;}int num = 0;for(int i = start; i < start + 3 && i < ip.length(); i++){num = num * 10 + Character.digit(ip.charAt(i), 10);if(num <= 255){ipBuffer.append(num);backtrack(result, ip, i + 1, step + 1, ipBuffer.append('.'));if(ipBuffer.length() >= String.valueOf(num).length() + 1){//深搜不成功时，从ipBuffer中删除当前深搜产生的中间值ipBuffer.delete(ipBuffer.length() - String.valueOf(num).length() - 1, ipBuffer.length());}}if(num == 0){break;}}}
}
这篇关于leetcode：Restore IP Addresses 【Java】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
