首页 > 代码库 > [leetcode] Restore IP Addresses
[leetcode] Restore IP Addresses
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)
https://oj.leetcode.com/problems/restore-ip-addresses/
思路：要打印所有的结果，只能dfs枚举了。
import java.util.ArrayList;import java.util.List;public class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<String>(); if (s.length() > 12) return res; StringBuilder sb = new StringBuilder(); dfs(res, sb, s, 0); return res; } private void dfs(List<String> res, StringBuilder sb, String s, int depth) { // System.out.println("sb:" + sb + ",s:" + s + ",depth:" + depth); if (depth > 4) return; if (depth == 4) { if (!s.equals("")) return; else { res.add(sb.toString().substring(0, sb.length() - 1)); } } for (int i = 1; i <= s.length() && i <= 3; i++) { String toInsert = s.substring(0, i); if (isValid(toInsert)) { sb.append(toInsert + "."); dfs(res, sb, s.substring(i), depth + 1); sb.delete(sb.length() - i - 1, sb.length()); } } } private boolean isValid(String toInsert) { int num = Integer.parseInt(toInsert); if (num > 255) return false; if (num != 0 && toInsert.startsWith("0") || num == 0 && !toInsert.equals("0")) return false; return true; } public static void main(String[] args) { String s = "010010"; System.out.println(new Solution().restoreIpAddresses(s)); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。