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

問題概要

0〜9の数字だけで構成された文字列が与えられたとします。この文字列を復元し、考えられるすべての有効なIPアドレスの組み合わせを求めることを目指します。ここで「有効なIPアドレス」とは、0から255までの範囲に収まる整数がちょうど4つ並び、それぞれが単一のドット（.）で区切られている形式を指します。

例として、入力が ip = "25525511136" の場合、出力は ["255.255.11.136", "255.255.111.36"] のようになります。

解法のアプローチ

この問題は、バックトラッキング（深さ優先探索）を用いることで効率的に解けます。以下の手順で実装を進めます。

1. convertToNum() 関数の定義

引数 s、start、end を受け取り、文字列 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 になり、かつ残りの文字がまだ存在する場合：残りの部分を convertToNum() で変換し、その値が 0 以上 255 以下であれば positions に追加します。addDots() で文字列を組み立て、その長さが元の文字列と一致した場合のみ result に追加します。この長さチェックによって、「01」のような先頭ゼロを含む不正なセグメントが自動的に除外されます。
• それ以外の場合：startIndex 以降の各切り出し位置 i について部分文字列を変換し、有効なら positions に push して再帰呼び出しを行います。再帰から戻ったら pop_back() で直前の選択を取り消し（バックトラック）、別の分割パターンを試します。

4. genIp() 関数

エントリポイントとなる関数です。結果用の配列 result と position を用意して solve() を呼び出し、完成した result を返します。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> 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]