C++で数字の文字列から有効なIPアドレスをすべて復元する方法

問題概要

数字のみで構成された文字列が与えられます。この文字列をもとに、考えられるすべての有効なIPアドレスの組み合わせを復元して返すことが求められます。有効なIPアドレスとは、0から255までの範囲の整数4つをドット（.）で区切って並べた形式のものです。

たとえば、入力が「25525511135」であれば、出力は「255.255.11.135」と「255.255.111.35」の2通りになります。

解決のアプローチ

この問題はバックトラッキング（深さ優先探索）を使うことで効率よく解けます。文字列を4つのセグメントに分割しながら、各セグメントが0～255の範囲に収まる有効な数値かどうかを順に検証していきます。全体の流れは次のとおりです。

1. convertToNum() 関数

文字列 s の start ～ end の範囲を数値に変換します。

• num := 0 で初期化します。

• i := start から end までループ処理を行います。

• num := (num * 10) + (s[i] - '0') で桁を追加していきます。

• 途中で num > 255 になった場合は、無効な値として 10000 を返します。

• ループが完了したら num を返します。

2. addDots() 関数

分割済みの数値リスト positions を受け取り、ドット区切りのIPアドレス形式の文字列を組み立てます。

• res := 空文字列 で初期化します。

• positions の各要素を文字列に変換して res に連結します。

• 最後の要素以外を処理した後には「.」を連結します。

• 完成した res を返します。

3. solve() 関数（再帰による探索）

引数は s、結果を格納する文字列配列 result、positions 配列、残りのドット数 dotCount（初期値3）、開始インデックス startIndex（初期値0）です。

• 終了条件： dotCount が 0 になり、かつ startIndex 以降にまだ文字が残っている場合、

  • temp := convertToNum(s, startIndex, s.size()-1) で最後のセグメントを評価します。

  • temp が 0 以上 255 以下であれば、positions の末尾に temp を追加します。

  • addDots(positions) で res を生成し、「res.size() - 3 == s.size()」が成立する場合のみ（＝先頭に不要な0が付いていないことの確認）result に res を追加します。

  • return で処理を終えます。

• 再帰ステップ： i := startIndex から s.size()-1 までループします。

  • temp := convertToNum(s, startIndex, i) で現在のセグメント候補を評価します。

  • temp が 0 以上 255 以下であれば、positions に追加して solve(s, result, positions, dotCount - 1, i + 1) を再帰呼び出しします。

  • 戻ってきたら positions の末尾要素を削除し（バックトラッキング）、別の分割パターンを試します。

4. genIp() 関数

• 結果用の配列 result と position を用意します。

• solve(s, result, position) を呼び出します。

• result を返します。

5. main 関数

main から genIp(A) を呼び出して結果を出力します。

実装例

それでは、実際の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> restoreIpAddresses(string A) {
   return genIp(A);
}};
main(){
   Solution ob;
   print_vector(ob.restoreIpAddresses("25525511135"));
}

入力

"25525511135"

出力

[255.255.11.135, 255.255.111.35]

ポイントの解説

このアルゴリズムの重要なポイントを整理します。

• 255超過の早期打ち切り： convertToNum() は桁を追加していく過程で num が 255 を超えた時点で即座に無効値（10000）を返すため、無駄な探索を大幅に省けます。

• 先頭ゼロの排除： 「res.size() - 3 == s.size()」というチェックにより、ドット3個分を除いた文字列長が元の文字列長と一致することを確認しています。「01」のような先頭ゼロを含むセグメントは数値化した際に桁が落ちて長さが合わなくなるため、不正なIPアドレスを自動的に除外できます。

• 計算量： 各セグメントの長さは最大3桁なので、探索空間は高々 3×3×3×3 = 81 通りに限定され、実質的に定数時間で処理できます。