本文主要是介绍LeetCode--93. Restore IP Addresses,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
93. Restore IP Addresses
这个问题基本上就是一个排列组合问题,首先ip地址是四位组成,每一位值都在0-255中取值,除了0以外,所有值都不能以0开头。所以在进行取子字符串时需要特别判断剔除这些情况。
class Solution {public static int[] record;public static LinkedList<String> ret;public List<String> restoreIpAddresses(String s) {record=new int[5];ret=new LinkedList<String>();recursive(0,s,0);return ret;}public static void recursive(int idx,String s,int start){if(idx==4){if(start>=s.length()){StringBuilder sb=new StringBuilder();for(int i=1;i<4;i++){sb.append(s.substring(record[i],record[i+1]));sb.append('.');}sb.append(s.substring(record[4]));ret.add(sb.toString());}return;}for(int i=start;i<start+3 && i<s.length();i++){String current=s.substring(start,i+1);int val=Integer.valueOf(current);if(i==start) //当待选第idx个子串长度为1时{record[idx+1]=start;recursive(idx+1,s,i+1);}else if(s.charAt(start)!='0' && val>=0 && val<=255){record[idx+1]=start;recursive(idx+1,s,i+1);} }}
}
这篇关于LeetCode--93. Restore IP Addresses的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!