C++で復元した後にすべての可能なIPアドレスを見つけるプログラム

数字のみの文字列があるとすると、可能なすべての有効なIPアドレスの組み合わせを形成して文字列を復元する必要があります。有効なIPアドレスは、単一のピリオド記号で区切られた正確に4つの整数（各整数は0〜255の範囲）で構成されていることがわかっています。

したがって、入力がip ="25525511136"の場合、出力は["254.25.40.123"、 "254.254.0.123"]

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

• 関数convertToNum（）を定義します。これには、s、start、endが必要です。
• num：=0
• iを初期化する場合：=開始、i <=終了の場合、更新（iを1つ増やす）、実行-
  • num：=（num * 10）+（s [i]- '0'のASCII）
  • num> 255の場合、-
    • 10000を返す
• return 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"。"
• return res
• 関数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のサイズと同じである場合、-
      • 結果の最後に解像度を挿入
  • 戻る
• iを初期化する場合：=startIndex、i
• temp：=convertToNum（s、startIndex、i）
• temp> =0かつtemp<=255の場合、-
  • 位置の最後に温度を挿入
  • solve（s、result、positions、dotCount-1、i + 1）
  • 位置から最後の要素を削除する

例（C ++）

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

#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> get_ip(string A) {
   return genIp(A);
}};
main(){
   Solution ob;
   string ip = "25525511136";
   print_vector(ob.get_ip(ip));
}

入力

25525511136

出力

[255.255.11.136, 255.255.111.36, ]