[LeetCode 93]Restore IP Addresses

题目链接：restore-ip-addresses

import java.util.ArrayList;import java.util.List;/** * 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) * */public class RestoreIPAddresses {//147 / 147 test cases passed.//Status: Accepted//Runtime: 236 ms//Submitted: 0 minutes ago//回溯法//时间复杂度O(n ^ 4) 空间复杂度O(n)public List<String> ips = new ArrayList<String>();public List<String> restoreIpAddresses(String s) {restoreIpAddresses(s, 0, "", 0);return ips;}/**** @param s原始ip字符串* @param cur原始ip字符串的游标，表示当前从哪开始取数* @param ip已经生成的ip的中间值* @param count纪录已经生成的点位个数*/public void restoreIpAddresses(String s, int cur, String ip, int count) {if(s.length() > 16) {return;}if(count == 4 && cur < s.length())return;if(cur == s.length()) {if (count == 4) {ips.add(ip.substring(0, ip.length() – 1));}return;}//点分组为一位数时int num1 = stringToInteger(s.substring(cur, cur + 1));if (num1 >= 0 && num1 < 10) {restoreIpAddresses(s, cur + 1, ip + num1 + ".", count + 1);}//点分组为两位数时if (cur + 1 < s.length()) {int num2 = stringToInteger(s.substring(cur, cur + 2));if (num2 > 9 && num2 < 100) {restoreIpAddresses(s, cur + 2, ip + num2 + ".", count + 1);}}//点分组为三位数时if (cur + 2 < s.length()) {int num3 = stringToInteger(s.substring(cur, cur + 3));if (num3 > 99 && num3 < 256) {restoreIpAddresses(s, cur + 3, ip + num3 + ".", count + 1);}}}//字符转换为数值public int stringToInteger(String s) {int n = 0;for (Character digit : s.toCharArray()) {n = n * 10 + digit – '0';}return n;}public static void main(String[] args) {System.out.println(new RestoreIPAddresses().restoreIpAddresses("25525511135"));System.out.println(new RestoreIPAddresses().restoreIpAddresses("1111"));}}

，有事者，事竟成;破釜沉舟，百二秦关终归楚;苦心人，