Welcome to Subscribe On Youtube

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

All Problems

All Solutions