Share my Java DFS Solution


  • 0
    M
            public List<String> restoreIpAddresses(String s) {
    		List<String> ips = new ArrayList<>();
    		if (s == null || s.length() < 4 || !s.matches("\\d+")) return ips;
    		dfs(s, new ArrayList<String>(), ips);
    		return ips;
    	}
    	
    	private void dfs(String s, List<String> pre, List<String> res) {
    		if (pre.size() == 4) {
    			if (s.isEmpty()) {
    				res.add(makeIP(pre));
    			}
    			return;
    		}
    		if (s.isEmpty()) return;
    		
    		for (int i = 1; i <= Math.min(s.length(), 3); ++i) {
    			String ip = s.substring(0, i);
    			if (ip.length() > 1 && ip.startsWith("0")) continue;
    			if (Integer.parseInt(ip) > 255) break;
    			pre.add(ip);
    			dfs(s.substring(i), pre, res);
    			pre.remove(pre.size() - 1);
    		}
    	}
    	
    	private String makeIP(List<String> list) {
    		String ip = "";
    		for (String s : list) ip += (ip.length() > 0 ? "." : "") + s;
    		return ip;
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.