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