20240309-16小六基础班练习（搜索算法）

ip地址

include

using namespace std;

bool isValidPart(const string& s, int start, int end) {

int len = end - start + 1;

// Check for leading zeros
if (len > 1 && s[start] == '0')
    return false;

// Convert string to integer
int num = stoi(s.substr(start, len));

// Check if number is between 0 and 255
return num >= 0 && num <= 255;

}

void backtrack(string& s, int start, int parts, vector& result, string current) {

// If reached the end of the string and used 4 parts, add current to result
if (start == s.length() && parts == 4) {
    result.push_back(current);
    return;
}

// If reached the end of the string or used all 4 parts, return
if (start == s.length() || parts == 4)
    return;

// Try adding '.' after each character
for (int len = 1; len <= 3 && start + len <= s.length(); ++len) {
    string part = s.substr(start, len);
    if (isValidPart(s, start, start + len - 1)) {
        if (current.empty()) {
            backtrack(s, start + len, parts + 1, result, part);
        } else {
            backtrack(s, start + len, parts + 1, result, current + "." + part);
        }
    }
}

}

vector restoreIpAddresses(string s) {

vector<string> result;
backtrack(s, 0, 0, result, "");
return result;

}

int main() {

string s;
cin >> s;

vector<string> validIPs = restoreIpAddresses(s);
for (const string& ip : validIPs) {
    cout << ip << endl;
}

return 0;

}

administer • 2个月前