Khôi phục địa chỉ IP trong C ++

Giả sử chúng ta có một chuỗi chỉ chứa các chữ số, chúng ta phải khôi phục nó bằng cách trả về tất cả các tổ hợp địa chỉ IP hợp lệ có thể có. Chúng tôi biết rằng một địa chỉ IP hợp lệ bao gồm chính xác bốn số nguyên (mỗi số nguyên nằm trong phạm vi từ 0 đến 255) được phân tách bằng các điểm duy nhất.

Vì vậy, nếu đầu vào là "25525511135", thì đầu ra sẽ là ["255.255.11.135", "255.255.111.35"]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm convertToNum (), hàm này sẽ có s, bắt đầu, kết thúc,

• num:=0

• để khởi tạo i:=start, khi i <=end, update (tăng i lên 1), do -

  • num:=(num * 10) + (s [i] - ASCII của '0')

  • nếu num> 255, thì -

    • trả lại 10000

• trả về số

• Xác định một hàm addDots (), hàm này sẽ có các vị trí,

• res:=chuỗi trống

• x:=0, posIndex:=0

• để khởi tạo i:=0, khi tôi

  • num:=vị trí [i]

  • tạo một chuỗi str1

  • temp:=num dưới dạng chuỗi

  • res:=res + temp

  • nếu tôi

    • res:=res nối "."

• trả lại res

• Xác định một hàm giải quyết (), điều này sẽ nhận s, một kết quả mảng chuỗi, một vị trí mảng, dotCount, đây là khởi tạo nó với 3, startIndex, đây là khởi tạo nó bằng 0,

• nếu không dotCount là khác 0 và ((kích thước của s - 1) - startIndex + 1) 1, thì -

  • temp:=convertToNum (s, startIndex, size of s)

  • nếu nhiệt độ> =0 và nhiệt độ <=255, thì−

    • chèn tạm thời vào cuối các vị trí

    • res:=addDots (vị trí)

    • nếu kích thước của res giống với kích thước của s, thì -

      • chèn res vào cuối kết quả

  • trở lại

• để khởi tạo i:=startIndex, khi tôi

  • temp:=convertToNum (s, startIndex, i)

  • nếu nhiệt độ> =0 và nhiệt độ <=255, thì -

    • chèn tạm thời vào cuối các vị trí

    • giải quyết (s, kết quả, vị trí, dotCount - 1, i + 1)

    • xóa phần tử cuối cùng khỏi các vị trí

• Xác định một genIp hàm, điều này sẽ lấy một chuỗi s,

• Xác định một kết quả mảng

• Xác định vị trí mảng

• giải quyết (s, kết quả, vị trí)

• trả về kết quả

• Từ phương thức chính, gọi genIp (A)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
   lli convertToNum(string s,int start, int end){
      lli num = 0;
      for (int i = start; i <= end; i++) {
         num = (num * 10) + (s[i] - '0');
         if (num > 255)
            return 10000;
      }
      return num;
}
string addDots(vector <int> positions){
   string res = "";
   int x = 0;
   int posIndex = 0;
   for (int i = 0; i < positions.size(); i++) {
      int num = positions[i];
      ostringstream str1;
      str1 << num;
      string temp = str1.str();
      res += temp;
      if (i < positions.size() - 1)
         res += ".";
   }
   return res;
}
void solve(string s, vector <string> &result,vector <int> positions, int dotCount = 3, int startIndex = 0){
   if (!dotCount && ((s.size() - 1) - startIndex + 1) >= 1) {
      int temp = convertToNum(s, startIndex, s.size() - 1);
      if (temp >= 0 && temp <= 255) {
         positions.push_back(temp);
         string res = addDots(positions);
         if (res.size() - 3 == s.size()) {
            result.push_back(res);
         }
      }
      return;
   }
   for (int i = startIndex; i < s.size(); i++) {
      int temp = convertToNum(s, startIndex, i);
      if (temp >= 0 && temp <= 255) {
         positions.push_back(temp);
         solve(s, result, positions, dotCount - 1, i + 1);
         positions.pop_back();
      }
   }
}
vector<string> genIp(string s){
   vector<string> result;
   vector<int> position;
   solve(s, result, position);
   return result;
}
vector<string> restoreIpAddresses(string A) {
   return genIp(A);
}};
main(){
   Solution ob;
   print_vector(ob.restoreIpAddresses("25525511135"));
}

Đầu vào

"25525511135"

Đầu ra

[255.255.11.135, 255.255.111.35, ]