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)

递归和非递归的写法都可以：

解法中给出的是递归的，要有些预判工作，否则会TLE；

非递归的就是要三层for循环遍历并3个点分位的位置并判断是否是合法ip。

解法

import java.util.ArrayList;

public class RestoreIPAddresses {
	private String s;
	private int N;

	public ArrayList
  
    restoreIpAddresses(String s) {
		if (s == null) {
			return null;
		}
		this.s = s;
		this.N = s.length();
		return solve(0, 4);
	}

	private ArrayList
   
     solve(int i, int k) { ArrayList
    
      list = new ArrayList
     
      (); if (i + k > N || N - i > 3 * k) { return list; } if (k == 1 && check(i, N - 1)) { list.add(s.substring(i)); } else { for (int j = 0; j < 3; ++j) { if (check(i, i + j)) { ArrayList
      
        subList = solve(i + j + 1, k - 1); for (String ip : subList) { list.add(s.substring(i, i + j + 1) + "." + ip); } } } } return list; } private final boolean check(int i, int j) { if (i < j - 2 || i > j || j >= N) { return false; } else if (i == j) { return true; } else if (i == j - 1) { return !s.substring(i, i + 1).equals("0"); } else { return !s.substring(i, i + 1).equals("0") && Integer.parseInt(s.substring(i, j + 1)) <= 255; } } }