93. Restore IP Addresses.md

93. Restore IP Addresses

Question

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Solution

• Method 1: dfs partition question

   class Solution {
   	public List<String> restoreIpAddresses(String s) {
   		List<String> result = new ArrayList<>();
   		if(s == null || s.length() < 4) return result;
   		dfs(result, new StringBuilder(), 0, s, 0);
   		return result;
   	}
   	private void dfs(List<String> result, StringBuilder sb, int start, String s, int count){
   		if(start == s.length() && count == 4){
   			sb.deleteCharAt(sb.length() - 1);
   			result.add(sb.toString());
   		}else if(count < 4){
   			for(int i = start + 1; (i <= start + 3) && (i <= s.length()); i++){
   				String sub = s.substring(start, i);
   				if(sub.charAt(0) == '0' && sub.length() != 1) return;
   				int cur = Integer.parseInt(sub);
   				if(cur >= 0 && cur <= 255){
   					int temp = sb.length();
   					sb.append(cur + ".");
   					dfs(result, sb, i, s, count + 1);
   					sb.delete(temp, sb.length());
   				}
   			}
   		}
   	}
   }

Amazon Session

• Method 1: recursion

   class Solution {
   	private List<String> result;
   	private String s;
   	public List<String> restoreIpAddresses(String s) {
   		this.result = new ArrayList<>();
   		this.s = s;
   		dfs(0, 0, "");
   		return this.result;
   	}
   	private void dfs(int index, int count, String temp){
   		if(index == s.length() && count == 4) this.result.add(temp);
   		else if(count < 4){
   			for(int i = index + 1; i <= index + 3 && i <= s.length(); i++){
   				String sub = s.substring(index, i);
   				int cur = Integer.parseInt(sub);
   				if(sub.charAt(0) == '0' && sub.length() != 1) return;
   				if(cur >= 0 && cur <= 255){
   					dfs(i, count + 1, temp + (temp.length() == 0 ? "": '.') + cur);
   				}
   			}
   		}
   	}
   }