C++でIPアドレスを復元する

数字のみを含む文字列があるとすると、考えられるすべての有効なIPアドレスの組み合わせを返すことによって文字列を復元する必要があります。有効なIPアドレスは、1つのポイントで区切られた正確に4つの整数（各整数は0〜255の範囲）で構成されていることがわかっています。

したがって、入力が「25525511135」の場合、出力は["255.255.11.135"、 "255.255.111.35"]

これを解決するには、次の手順に従います-

• 関数convertToNum（）を定義します。これには、s、start、end、

  が必要です。

• num：=0

• 初期化i：=startの場合、i <=endの場合、更新（iを1増やします）、do-

  • num：=（num * 10）+（s [i]- '0'のASCII）

  • num> 255の場合、-

    • 10000を返す

• numを返す

• 関数addDots（）を定義します。これは位置を取ります

• res：=空白の文字列

• x：=0、posIndex：=0

• 初期化i：=0の場合、i <位置のサイズの場合、更新（iを1増やします）、実行-

  • num：=position [i]

  • 1つの文字列str1を作成します

  • temp：=num as string

  • res：=res + temp

  • i <位置のサイズの場合、-

    • res：=resconcatenate"。"

• 解像度を返す

• 関数solve（）を定義します。これには、s、1つの文字列配列の結果、配列の位置、dotCountが必要です。これは、3で初期化され、startIndexであり、0で初期化されます。

• dotCountがゼロ以外であり、（（sのサイズ-1）-startIndex + 1）1である場合、-

  • temp：=convertToNum（s、startIndex、size of s）

  • temp> =0かつtemp<=255の場合、-

    • 位置の最後に温度を挿入

    • res：=addDots（positions）

    • resのサイズがsのサイズと同じである場合、-

      • 結果の最後にresを挿入します

  • 戻る

• 初期化i：=startIndexの場合、i

  • temp：=convertToNum（s、startIndex、i）

  • temp> =0かつtemp<=255の場合、-

    • 位置の最後に温度を挿入

    • 解決（s、結果、位置、dotCount-1、i + 1）

    • 位置から最後の要素を削除する

• 1つの関数genIpを定義します。これには、文字列sが必要です。

• 配列結果を定義する

• 配列の位置を定義する

• 解決（s、結果、位置）

• 結果を返す

• メインメソッドからgenIp（A）

  を呼び出します

例

理解を深めるために、次の実装を見てみましょう-

#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"));
}

入力

"25525511135"

出力

[255.255.11.135, 255.255.111.35, ]