Question

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

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

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

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]

Example 3:

Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Constraints:

1 <= s.length <= 20
s consists of digits only.

Algorithm

In this problem, we need to add three dots to an input character string and divide it into four segments, where each segment must be legal. Our task is to find all possible situations that meet the given criteria.

Through previous problem-solving experience, we have learned that whenever a subsequence or registration problem of a string is encountered, we first consider using dynamic programming (DP). On the other hand, when we need to request all possible situations, we first consider using recursion.

In this case, we need to find all possible legal segmentations, which is more in line with the second case, i.e., we must use recursion to solve this problem.

We represent the number of segments that still need to be divided by k. If k equals 0, it means that we have added three dots and formed four segments. At this point, if the string is empty, we save the current divided result. If k is not 0, then for each segment, we try using one, two, and three digits and judge whether it is legal or not. If it is legal, we call recursion to continue dividing the remaining strings and finally sum up all legal combinations.

Code

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;
	    }
	}
}

############

class Solution {
    private List<String> ans;

    public List<String> restoreIpAddresses(String s) {
        ans = new ArrayList<>();
        dfs(s, new ArrayList<>());
        return ans;
    }

    private void dfs(String s, List<String> t) {
        if (t.size() == 4) {
            if ("".equals(s)) {
                ans.add(String.join(".", t));
            }
            return;
        }
        for (int i = 1; i < Math.min(4, s.length() + 1); ++i) {
            String c = s.substring(0, i);
            if (check(c)) {
                t.add(c);
                dfs(s.substring(i), t);
                t.remove(t.size() - 1);
            }
        }
    }

    private boolean check(String s) {
        if ("".equals(s)) {
            return false;
        }
        int num = Integer.parseInt(s);
        if (num > 255) {
            return false;
        }
        if (s.charAt(0) == '0' && s.length() > 1) {
            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:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def check(s):
            if not (0 <= int(s) <= 255):
                return False
            if s[0] == '0' and len(s) > 1:
                return False
            return True

        def dfs(s, t):
            if len(t) == 4:
                if not s:
                    ans.append('.'.join(t))
                return
            for i in range(1, min(4, len(s) + 1)):
                if check(s[:i]):
                    t.append(s[:i])
                    dfs(s[i:], t)
                    t.pop()

        ans = []
        dfs(s, [])
        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

func restoreIpAddresses(s string) []string {
	check := func(s string) bool {
		if i, _ := strconv.Atoi(s); i > 255 {
			return false
		}
		if s[0] == '0' && len(s) > 1 {
			return false
		}
		return true
	}
	var ans []string
	var dfs func(s string, t []string)
	dfs = func(s string, t []string) {
		if len(t) == 4 {
			if s == "" {
				ans = append(ans, strings.Join(t, "."))
			}
			return
		}
		for i := 1; i < 4 && i < len(s)+1; i++ {
			if check(s[0:i]) {
				t = append(t, s[0:i])
				dfs(s[i:], t)
				t = t[0 : len(t)-1]
			}
		}
	}
	var t []string
	dfs(s, t)
	return ans
}

using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<string> RestoreIpAddresses(string s) {
        if (s.Length > 12) return new List<string>();
        var results = new HashSet<string>();
        for (var i = 0; i < s.Length - 3; ++i)
        {
            for (var j = i + 1; j < s.Length - 2; ++j)
            {
                for (var k = j + 1; k < s.Length - 1; ++k)
                {
                    var part1 = Normalize(s.Substring(0, i + 1));
                    var part2 = Normalize(s.Substring(i + 1, j - i));
                    var part3 = Normalize(s.Substring(j + 1, k - j));
                    var part4 = Normalize(s.Substring(k + 1));
                    
                    if (part1 != null && part2 != null && part3 != null && part4 != null)
                    {
                        results.Add(string.Format("{0}.{1}.{2}.{3}", part1, part2, part3, part4));
                    }
                }
            }
        }
        
        return results.ToList();
    }
    
    private string Normalize(string part)
    {
        if (part == "0") return part;
        if (part[0] == '0') return null;
        byte temp = 0;
        if (byte.TryParse(part, out temp))
        {
            return part;
        }
        else
        {
            return null;
        }
    }
}

93 - Restore IP Addresses

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions