这道题核心思想是DFS求解，一个IP地址有四段，每段有1到3个字符， public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<String>(); if (s == null || s.length() < 4 || s.length() > 12) { return res; } StringBuffer tmp = new StringBuffer(); dfs(0, 0, s, tmp, res); System.out.println(res.toString()); return res; } public void dfs(int count, int index, String s, StringBuffer tmp, List<String> res) { if (count == 4 && index == s.length()) { res.add(tmp.toString().substring(0,tmp.length()-1)); return; } else{ for(int i=1;i<=3 && index+i<=s.length();i++){ String tmpStr=s.substring(index,index+i); if(isValid(tmpStr)){ int bt=tmp.length(); int ed=tmp.length()+tmpStr.length(); tmp.append(tmpStr).append("."); dfs(count+1, index+i, s, tmp, res); tmp.delete(bt,ed+1); } } } } public boolean isValid(String s){ if(s.charAt(0)=='0'){ return s.equals("0"); } Integer num=Integer.parseInt(s); return num>0 && num<=255; } public static void main(String[] args) { LeetCode code=new LeetCode(); List<String> res=code.restoreIpAddresses("25525511135"); }
转载请注明原文地址: https://www.6miu.com/read-78820.html
