学步园

简单的枚举，关键是corner case。 分成四段，不能多不能少，每段的数字只能从0-255，但是注意0开头的情况，"01","025"都是不行。

import java.util.*;

public class Solution {

	public List<String> restoreIpAddresses(String s) {
		List<String> ips = new LinkedList<String>();
		List<String> comb = new LinkedList<String>();
		restoreIP(s, ips, comb, 0);

		return ips;
	}

	public void restoreIP(String s, List<String> ips, List<String> comb, int k) {

		if (comb.size() > 4)
			return;

		if (k == s.length()) {
			if (comb.size() == 4) {
				String ip = comb.get(0);
				for (int i = 1; i < 4; i++) {
					ip += "." + comb.get(i);
				}
				ips.add(ip);
			}
			return;
		}

		if (k + 1 <= s.length()) {
			comb.add(s.substring(k, k + 1));
			restoreIP(s, ips, comb, k + 1);
			comb.remove(comb.size() - 1);
		}

		if (k + 2 <= s.length() && s.charAt(k) != '0') {
			comb.add(s.substring(k, k + 2));
			restoreIP(s, ips, comb, k + 2);
			comb.remove(comb.size() - 1);
		}

		if (k + 3 <= s.length() && s.charAt(k) > '0' && s.substring(k,k+3).compareTo("256")<0) {
			
			comb.add(s.substring(k, k + 3));
			restoreIP(s, ips, comb, k + 3);
			comb.remove(comb.size() - 1);
		}
	}

	public static void main(String[] args) {
		Solution sol = new Solution();
		List<String> ips = sol.restoreIpAddresses("000256");

		for (String str : ips)
			System.out.println(str);
	}
}