93. Restore IP Addresses
有效的 IP 地址由四個用單個點分隔的整數組成。每個整數在 0 到 255（包含）之間，且不能有前導零。
例如，"0.1.2.201" 和 "192.168.1.1" 是有效的 IP 地址，但 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是無效的 IP 地址。
給定一個只包含數字的字符串 s，返回通過在 s 中插入點可以形成的所有可能的有效 IP 地址。你不能重新排列或移除 s 中的任何數字。你可以以任意順序返回有效的 IP 地址。
範例 1：
輸入：s = "25525511135" 輸出：["255.255.11.135","255.255.111.35"]
Python
from typing import List
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
def is_valid(segment):
# A segment is valid if it is less than or equal to 255 and does not have leading zeros
return int(segment) <= 255 if segment[0] != '0' else len(segment) == 1
def backtrack(start=0, path=[]):
# If we have 4 segments and we are at the end of the string, it's a valid IP address
if len(path) == 4:
if start == len(s):
result.append(".".join(path))
return
# Try all possible segments of length 1 to 3
for length in range(1, 4):
if start + length <= len(s):
segment = s[start:start + length]
if is_valid(segment):
backtrack(start + length, path + [segment])
result = []
backtrack()
return result
16.48MB, 38ms
C++
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> result;
vector<string> path;
backtrack(s, 0, path, result);
return result;
}
private:
void backtrack(const string& s, int start, vector<string>& path, vector<string>& result) {
// If we have 4 segments and we are at the end of the string, it's a valid IP address
if (path.size() == 4) {
if (start == s.length()) {
result.push_back(join(path, "."));
}
return;
}
// Try all possible segments of length 1 to 3
for (int length = 1; length <= 3; ++length) {
if (start + length <= s.length()) {
string segment = s.substr(start, length);
if (isValid(segment)) {
path.push_back(segment);
backtrack(s, start + length, path, result);
path.pop_back();
}
}
}
}
bool isValid(const string& segment) {
if (segment.length() > 3 || (segment[0] == '0' && segment.length() > 1) || stoi(segment) > 255) {
return false;
}
return true;
}
string join(const vector<string>& path, const string& delimiter) {
string result;
for (int i = 0; i < path.size(); ++i) {
if (i > 0) result += delimiter;
result += path[i];
}
return result;
}
};
10.72MB, 5ms
Javascript
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
const result = [];
const isValid = (segment) => {
if (segment.length > 3 || (segment[0] === '0' && segment.length > 1) || parseInt(segment) > 255) {
return false;
}
return true;
};
const backtrack = (start, path) => {
// If we have 4 segments and we are at the end of the string, it's a valid IP address
if (path.length === 4) {
if (start === s.length) {
result.push(path.join('.'));
}
return;
}
// Try all possible segments of length 1 to 3
for (let length = 1; length <= 3; length++) {
if (start + length <= s.length) {
const segment = s.substring(start, start + length);
if (isValid(segment)) {
path.push(segment);
backtrack(start + length, path);
path.pop();
}
}
}
};
backtrack(0, []);
return result;
};
50.40MB, 63ms
