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)

看到这个题目首先就想回溯的思想，所以写出来AC的java代码如下：

public class Solution {	private List<String> ans = new ArrayList<String>();	public List<String> restoreIpAddresses(String s) {		search(s, "", 0);		return ans;	}	public void search(String dataString, String temp, int level) {		// 结束条件：递归了第四层，并且dataString为空		if (level == 4) {			if (dataString.length() == 0) {				ans.add(temp);			}		} else {			int possible = dataString.length() > 3 ? 3 : dataString.length();			for (int i = 1; i <= possible; i++) {				String partofTemp = dataString.substring(0, i);				if (isValidSegment(partofTemp)) {					// store previous temp					String oldTemp = temp;					if (level == 0) {						temp = partofTemp;					} else {						temp += "." + partofTemp;					}					search(dataString.substring(i), temp, level + 1);					temp = oldTemp;				}			}		}	}	public boolean isValidSegment(String s) {		if (s.charAt(0) == '0')			return s.length() == 1;		Integer result = Integer.parseInt(s);		if (result > 255)			return false;		return true;	}}

后面看到一种其他思路就是利用三个for循环进行判断。

Restore IP Addresses