93.Restore IP Addresses === ###### tags: `Medium`,`String`,`Backtracking` [93. Restore IP Addresses](https://leetcode.com/problems/restore-ip-addresses/) ### 題目描述 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. ### 解答 #### C++ ##### 作法 1. backtracking走一遍 ```cpp= class Solution { public: vector<string> ans; void BT(const string &s, string address = "", string cur = "", int i = 0) { if (i == s.size()) { if (cur.empty() && count(address.begin(), address.end(), '.') == 3) { ans.push_back(address); } return; } if (!cur.empty() && stoi(cur) == 0) return; cur.push_back(s[i]); if (stoi(cur) > 255) return; BT(s, address, cur, i + 1); if (address.empty()) { BT(s, cur, "", i + 1); } else { BT(s, address + "." + cur, "", i + 1); } } vector<string> restoreIpAddresses(string s) { BT(s); return ans; } }; ``` > [name=Yen-Chi Chen][time=Sat, Jan 21, 2023] #### Python ```python= class Solution: def restoreIpAddresses(self, s: str) -> List[str]: ans = [] def BT(address = [int(s[0])], i = 1): if i == len(s): if len(address) == 4: ans.append('.'.join(map(str, address))) return old = address[-1] new = old * 10 + int(s[i]) if old != 0 and new <= 255: address[-1] = new BT(address, i + 1) address[-1] = old if len(address) < 4: BT(address + [int(s[i])], i + 1) BT() return ans ``` > [name=Yen-Chi Chen][time=Sat, Jan 21, 2023] ```python= class Solution: def restoreIpAddresses(self, s: str) -> List[str]: def check0_255(s): x = int(s) return x>0 and x<=255 def dfs(_s, pnts): #print('##', _s, pnts) if len(_s) > 3*(pnts+1) or len(_s) == 0: return [] if pnts == 0: #print('##', pnts, _s, len(_s)) if len(_s) > 4 or len(_s) == 0: return [] if _s == '0': return [['0']] if _s[0] == '0': return [] if check0_255(_s): return [ [_s] ] return [] if _s[0] == '0': result = [] for item in dfs(_s[1:], pnts-1): #print(item) result.append( ['0'] + item) return result result = [] for digit in [1,2,3]: x = int( _s[0:digit] ) #print(pnts, x) if check0_255(x): for item in dfs(_s[digit:], pnts-1): #print(pnts, _s, item) result.append( [str(x)] + item) #print(pnts, _s, result) return result Q = dfs(s, 3) return [ ".".join(x) for x in Q] ``` ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)