免费网站建设 免备案,机械类外贸网站建设,网站开发服务费计入哪个科目,搞网站难度#xff1a; 中等通过率#xff1a; 30.2%题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
题目描述
给定一个只包含数字的字符串#xff0c;复原它并返回所有可能的 IP 地址格式。
示例:
输入: 25525511135 中等通过率 30.2%题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
题目描述
给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。
示例:
输入: 25525511135
输出: [255.255.11.135, 255.255.111.35]
解法
此题使用递归来解答相当容易每次从字符串前分别取 1,2,3 个字符如果符合要求就加入 parts 中在余下的字符串中继续添加下一部分。当发现 parts 长度为 4且没有剩余的字符时将其加入到结果中。如果长度已经为 4但余下字符尚不为空说明 parts 中的解不对因此要退出递归。当余下字符串不够长了此时也退出。
整个字符串可以在多处断开因此所有可能的分隔情况构成了一棵搜索树。这里采用了深度优先去搜索这棵树在合适的条件下对树进行减枝。在搜索到符合要求的结果是将其保存。
class Solution {
public:vectorstring restoreIpAddresses(string s) {vectorstring result;vectorstring parts;dfs(s, 0, parts, result);return result;}void dfs(const string s, size_t start, vectorstring parts, vectorstring result){if(start s.size() parts.size() 4){result.push_back(parts[0] . parts[1] . parts[2] . parts[3]);return;}if(parts.size() 4){return;}// 余下的字符串不够长了if(s.size() - start (4 - parts.size())){return;}// 余下的字符串太长if(s.size() - start (4 - parts.size()) * 3){return;}int num 0;size_t end min(start3, s.size());for(size_t i start; i end; i){num num * 10 (s[i] - 0);if(num 255){continue;}parts.push_back(s.substr(start, i - start 1));dfs(s, i 1, parts, result);parts.pop_back();// 012 跳过这样的// 当首字符为 0 时后面的都不用再看了if(num 0){break;}}}
};
