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