問(wèn)題
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
例子
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
分析
dfs，枚舉各種分割的情況迁筛，如果得到的結(jié)果滿(mǎn)足下面的所有條件策州，則是一個(gè)合法的IP地址：
- 字符串被3個(gè).號(hào)分成4個(gè)部分
- 每部分的值在[0-255]范圍內(nèi)
- 除非等于0翰灾，否則每部分?jǐn)?shù)字的開(kāi)頭不能是0
要點(diǎn)
dfs即横，及時(shí)裁剪不符合條件的狀態(tài)
時(shí)間復(fù)雜度
O(3^3)旁蔼，因?yàn)槊總€(gè).號(hào)的插入位置都可以有三種選擇
空間復(fù)雜度
O(1)
代碼
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
dfs(res, s);
return res;
}
private:
// ip地址的格式：XXX.XXX.XXX.XXX适肠，XXX∈[0,255]
// len表示當(dāng)前ip的長(zhǎng)度，part表示當(dāng)前ip已經(jīng)包含了幾部分（.號(hào)將ip地址分為四部分）
void dfs(vector<string> &res, const string &s, string ip = "", int len = 0, int part = 0) {
if (part > 4) return;
if (part == 4 && len == s.size()) {
ip.pop_back();
res.push_back(ip);
return;
}
int num = 0;
// 每部分?jǐn)?shù)字的開(kāi)頭不能是0效床，除非數(shù)字本身就是0
int end = min(s[len] == '0' ? 1 : 3, (int)s.size() - len);
for (int i = 0; i < end; i++) {
num = 10 * num + s[len + i] - '0';
if (num > 255) break; // 每部分?jǐn)?shù)字要在[0-255]范圍內(nèi)
ip += s[len + i];
dfs(res, s, ip + '.', len + i + 1, part + 1);
}
}
};
