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<String> restoreIpAddresses(String s) {
		if (s == null) {
			return null;
		}
		this.s = s;
		this.N = s.length();
		return solve(0, 4);
	}

	private ArrayList<String> solve(int i, int k) {
		ArrayList<String> list = new ArrayList<String>();
		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<String> 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;
		}
	}
}

LeetCode | Restore IP Addresses,布布扣,bubuko.com

LeetCode | Restore IP Addresses

原文：http://blog.csdn.net/perfect8886/article/details/20400659