leetcode 93 复原ip地址
给定一个只包含数字的字符串,复原它并返回全部可能的 IP 地址格式。c++
示例:web
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]svg
.
分割ip为四段,每段的值都不能大于255,且若是本段若是以0开始,那么只能是0,不能带有其余的数字class Solution { vector<string> result; vector<string> tmp; bool isIPSegment(const string& s){ //以0开始的段,只能出现一个0 if(s[0] == '0') return s.size() -1 == 0; //不然值应该小于256 stringstream os(s); int i; os >> i; return i <= 255; } void backtrace(const string& s,int index,int level){ if(level == 4){ string t; for(const auto& it : tmp) t += it; result.push_back(std::move(t)); return; } //最后一段,须要消费掉剩余的字符串 if(level == 3){ if(s.size() - 3 > index || s.size() <= index || !isIPSegment(s.substr(index))) return; tmp.push_back(s.substr(index)); backtrace(s,index,level+1); tmp.pop_back(); return; } //每段最多消费3个字符 int size = min((int)s.size(),index + 3); // i 表示右边界,左边右开 for(int i = index+1;i <= size; ++i){ string sub = s.substr(index,i-index); if(!isIPSegment(sub)) return; tmp.push_back(s.substr(index,i-index)+"."); backtrace(s,i,level+1); tmp.pop_back(); } } public: vector<string> restoreIpAddresses(string s) { backtrace(s,0,0); return result; } };