Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example:
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Solution: DFS
The range of valid numbers is [0, 255]
Time complexity: O(3^4)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string> ans; string ip; dfs(0, s, ip, ans); return ans; } private: void dfs(int d, string s, string ip, vector<string> &ans) { int l = s.length(); if (d == 4) { if (l == 0) ans.push_back(ip); return; } for (int i = 1; i <= min(3, s[0] == '0' ? 1 : l); i++) { string ss = s.substr(0, i); if (i == 3 && stoi(ss) > 255) return; dfs(d + 1, s.substr(i), ip + (d == 0 ? "" : ".") + ss , ans); } } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment