Рубрики

Программа для генерации всех возможных действительных IP-адресов из заданной строки | Набор 2

Получив строку, содержащую только цифры, восстановите ее, вернув все возможные допустимые комбинации IP-адресов.
Действительный IP-адрес должен быть в форме ABCD , где A , B , C и D являются числами от 0 до 255 . Числа не могут иметь префикс 0, если они не равны 0 .

Примеры:

Input: str = “25525511135”
Output:
255.255.11.135
255.255.111.35

Input: str = “11111011111”
Output:
111.110.11.111
111.110.111.11

Подход: эту проблему можно решить с помощью возврата . В каждом вызове у нас есть три варианта создания единого блока номеров действительного IP-адреса:

  1. Либо выберите только одну цифру, добавьте точку и перейдите к выбору других блоков (дальнейшие вызовы функций).
  2. Или выберите две цифры одновременно, добавьте точку и двигайтесь дальше.
  3. Или выберите три последовательные цифры и перейдите к следующему блоку.

В конце четвертого блока, если все цифры были использованы и сгенерированный адрес является действительным IP-адресом, затем добавьте его к результатам и затем верните обратно, удалив цифры, выбранные в предыдущем вызове.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <iostream>
#include <vector>

using namespace std;

  
// Функция для получения всех действительных ip-адресов

void GetAllValidIpAddress(vector<string>& result,

                          string givenString, int index,

                          int count, string ipAddress)

{

  

    // Если индекс больше, чем заданный размер строки

    // и у нас есть четыре блока

    if (givenString.size() == index && count == 4) {

  

        // Удалить последнюю точку

        ipAddress.pop_back();

  

        // Добавить ip-адрес к результатам

        result.push_back(ipAddress);

        return;

    }

  

    // Добавить один индекс в ip-адрес

    if (givenString.size() < index + 1)

        return;

  

    // Выберите одну цифру и вызовите

    // та же функция для других блоков

    ipAddress = ipAddress

                + givenString.substr(index, 1) + '.';

    GetAllValidIpAddress(result, givenString, index + 1,

                         count + 1, ipAddress);

  

    // Возврат для создания другого возможного IP-адреса

    // Таким образом, мы удаляем два индекса (один для цифры

    // и другое для точки) с конца

    ipAddress.erase(ipAddress.end() - 2, ipAddress.end());

  

    // Выбираем две последовательные цифры и вызываем

    // та же функция для других блоков

    if (givenString.size() < index + 2

        || givenString[index] == '0')

        return;

    ipAddress = ipAddress + givenString.substr(index, 2) + '.';

    GetAllValidIpAddress(result, givenString, index + 2,

                         count + 1, ipAddress);

  

    // Возврат для создания другого возможного IP-адреса

    // Таким образом, мы удаляем три индекса с конца

    ipAddress.erase(ipAddress.end() - 3, ipAddress.end());

  

    // Выберите три цифры подряд и вызовите

    // та же функция для других блоков

    if (givenString.size() < index + 3

        || stoi(givenString.substr(index, 3)) > 255)

        return;

    ipAddress += givenString.substr(index, 3) + '.';

    GetAllValidIpAddress(result, givenString, index + 3,

                         count + 1, ipAddress);

  

    // Возврат для создания другого возможного IP-адреса

    // Таким образом, мы удаляем четыре индекса с конца

    ipAddress.erase(ipAddress.end() - 4, ipAddress.end());

}

  
// Код драйвера

int main()

{

    string givenString = "25525511135";

  

    // Заполняем вектор результата всеми действительными ip-адресами

    vector<string> result;

    GetAllValidIpAddress(result, givenString, 0, 0, "");

  

    // Распечатать все сгенерированные ip-адреса

    for (int i = 0; i < result.size(); i++) {

        cout << result[i] << "\n";

    }

}

python3

# Python3 реализация подхода

  
# Функция для получения всех действительных ip-адресов

def GetAllValidIpAddress(result, givenString,

                         index, count, ipAddress) :

  

    # Если индекс больше, чем заданный размер строки

    # и у нас есть четыре блока

    if (len(givenString) == index and count == 4) :

  

        # Удалить последнюю точку

        ipAddress.pop(); 

  

        # Добавить ip-адрес к результатам

        result.append(ipAddress); 

        return

  

    # Добавить один индекс в ip-адрес

    if (len(givenString) < index + 1) :

        return

  

    # Выберите одну цифру и позвоните

    # та же функция для других блоков

    ipAddress = (ipAddress + 

                 givenString[index : index + 1] + ['.']); 

      

    GetAllValidIpAddress(result, givenString, index + 1,

                                 count + 1, ipAddress); 

  

    # Возврат для создания другого возможного IP-адреса

    # Таким образом, мы удаляем два индекса (один для цифры

    # и другие для точки) с конца

    ipAddress = ipAddress[:-2];

  

    # Выберите две цифры подряд и позвоните

    # та же функция для других блоков

    if (len(givenString) < index + 2 or 

            givenString[index] == '0') :

        return

          

    ipAddress = ipAddress + givenString[index:index + 2] + ['.']; 

    GetAllValidIpAddress(result, givenString, index + 2

                                  count + 1, ipAddress); 

  

    # Возврат для создания другого возможного IP-адреса

    # Таким образом, мы удаляем три индекса с конца

    ipAddress = ipAddress[:-3]; 

  

    # Выберите три цифры подряд и позвоните

    # та же функция для других блоков

    if (len(givenString)< index + 3 or 

        int("".join(givenString[index:index + 3])) > 255) :

        return

    ipAddress += givenString[index:index + 3] + ['.']; 

    GetAllValidIpAddress(result, givenString, 

                         index + 3, count + 1, ipAddress); 

  

    # Возврат для создания другого возможного IP-адреса

    # Таким образом, мы удаляем четыре индекса с конца

    ipAddress = ipAddress[:-4]; 

  
# Код драйвера

if __name__ == "__main__"

    givenString = list("25525511135"); 

  

    # Заполнить вектор результата всеми действительными ip-адресами

    result = [] ; 

    GetAllValidIpAddress(result, givenString, 0, 0, []); 

  

    # Распечатать все сгенерированные ip-адреса

    for i in range(len(result)) :

        print("".join(result[i])); 

          
# Этот код предоставлен Ankitrai01

Выход:

255.255.11.135
255.255.111.35

Рекомендуемые посты:

Программа для генерации всех возможных действительных IP-адресов из заданной строки | Набор 2

0.00 (0%) 0 votes