Question

Formatted question description: https://leetcode.ca/all/93.html

93	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)

Algorithm

For the segmentation problem of character strings, add three dots to the input character string and divide the character string into four segments. Each segment must be legal. Seek all possible situations.

Based on so many questions so far, two experiences have been drawn.

• One is that as long as the subsequence or registration problem of a string is encountered, the dynamic programming DP is first considered;
• the other is that as long as all possible situations need to be requested, recursion is first considered.

This question is not a question of seeking a subsequence or registration of a string, but more in line with the second case, so we have to use recursion to solve it.

We use k to represent the number of segments that still need to be divided. If k = 0, it means that three points have been added and four segments have been formed. If the string is just empty at this time, the current divided result will be saved. If k != 0, then for each segment, we use one, two, and three digits to try and judge whether it is legal or not. If it is legal, call recursion to continue dividing the remaining strings, and finally sum All legal combinations

Code

Java

• Java
• C++
• Python

• import java.util.ArrayList;
  import java.util.List;
  
  public class Restore_IP_Addresses {
  
  	public static void main(String[] args) {
  
  		// @note:@memorize: test substring boundary
  		String a = "abc";
  		// a = a.substring(0, 4); // String index out of range: 4
  		a = a.substring(0, 3); // ok
  		System.out.println(a);
  
  		Restore_IP_Addresses out = new Restore_IP_Addresses();
  		Solution s = out.new Solution();
  
  		for (String each: (s.restoreIpAddresses("25525511135"))) {
  			System.out.println(each);
  		}
  	}
  
  	List<String> list = new ArrayList<>();
  
  	public class Solution {
  	    public List<String> restoreIpAddresses(String s) {
  
  	    	if (s.length() < 4 || s.length() > 12 || !s.matches("\\d+")) {
  	        	return list;
  	        }
  
  	    	restore(s, "", 0);
  
  	    	return list;
  	    }
  
  	    // seg: segment, in total 4
  	    private void restore(String s, String result, int seg) {
  	    	if (seg == 4) {
  	    		if (s.length() == 0) {
  
  	    			// remove last "."
  	    			result = result.substring(0, result.length() - 1);
  
  	    			list.add(result);
  	    		}
  
  	    		return;
  	    	}
  
  	    	// for (int i = 0; i < 3; i++) { // @note: out of boundary
  	    	for (int i = 0; i < 3 && i < s.length(); i++) {
  	    		String thisSeg = s.substring(0, i + 1);
  
  	    		if (isValid(thisSeg)) {
  	    			restore(s.substring(i + 1), result + thisSeg + ".", seg + 1);
  	    		}
  	    	}
  	    }
  
  	    private boolean isValid(String s) {
  
  	    	// can NOT be: 10.01.1.1
  	    	if (s.length() > 1 && s.startsWith("0")) {
  	    		return false;
  	    	}
  
  	    	int n = Integer.valueOf(s);
  	    	if (n > 255) {
  	    		return false;
  	    	}
  
  	    	return true;
  	    }
  	}
  }
  

• // OJ: https://leetcode.com/problems/restore-ip-addresses
  // Time: O(1)
  // Space: O(1)
  class Solution {
  private:
    vector<string> ans;
    void dfs(string &s, int start, int pos, string &ip) {
      if (pos == 4) {
        if (start == s.size()) ans.push_back(ip);
        return;
      }
      int i = 0;
      for (int num = 0; i < 3 && start + i < s.size(); ++i) {
        num = num * 10 + s[start + i] - '0';
        if (num > 255 || (s[start] == '0' && i)) break;
        ip.push_back(s[start + i]);
        if (pos < 3) ip.push_back('.');
        dfs(s, start + i + 1, pos + 1, ip);
        if (pos < 3) ip.pop_back();
      }
      while (i--) ip.pop_back();
    }
  public:
    vector<string> restoreIpAddresses(string s) {
      string ip;
      dfs(s, 0, 0, ip);
      return ans;
    }
  };
  

• class Solution(object):
    def restoreIpAddresses(self, s):
      """
      :type s: str
      :rtype: List[str]
      """
      ans = []
      n = len(s)
  
      def isValid(num):
        if len(num) == 1:
          return True
        if len(num) > 1 and num[0] != "0" and int(num) <= 255:
          return True
        return False
  
      for i in range(0, min(3, n - 3)):
        a = s[:i + 1]
        if not isValid(a):
          break
        for j in range(i + 1, min(i + 4, n - 2)):
          b = s[i + 1:j + 1]
          if not isValid(b):
            break
          for k in range(j + 1, min(j + 4, n - 1)):
            c = s[j + 1:k + 1]
            d = s[k + 1:]
            if not isValid(c):
              break
            if not isValid(d):
              continue
            ans.append("{}.{}.{}.{}".format(a, b, c, d))
      return ans
  
  

All Problems

All Solutions