从给定字符串生成所有可能的有效IP地址的程序|套装2

本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Python3

给定仅包含数字的字符串, 请通过返回所有可能的有效IP地址组合来还原它。

有效的IP地址必须采用以下形式：

A B C D

, 在哪里

一种

,

乙

,

C

和

d

是数字

0 – 255

。数字不能是

0

带前缀, 除非它们是

0

.

例子：

输入：str =" 25525511135"输出：255.255.11.135 255.255.111.35输入：str =" 11111011111"输出：111.110.11.111 111.110.111.11

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

方法：这个问题可以用解决回溯。在每个呼叫中​​, 我们都有三个选项来创建一个有效IP地址的单个数字块：

1. 仅选择一个数字, 添加一个点, 然后移至选择其他块(其他函数调用)。
2. 或同时选择两个数字, 添加一个点并进一步移动。
3. 或者选择三个连续的数字并移动到下一个块。

在第四个块的末尾, 如果所有数字都已使用并且生成的地址是有效的ip地址, 则将其添加到结果中, 然后通过删除在先前调用中选择的数字进行回溯。

下面是上述方法的实现：

C ++

// C++ implementation of the approach
#include <iostream>
#include <vector>
using namespace std;
  
// Function to get all the valid ip-addresses
void GetAllValidIpAddress(vector<string>& result, string givenString, int index, int count, string ipAddress)
{
  
     // If index greater than givenString size
     // and we have four block
     if (givenString.size() == index && count == 4) {
  
         // Remove the last dot
         ipAddress.pop_back();
  
         // Add ip-address to the results
         result.push_back(ipAddress);
         return ;
     }
  
     // To add one index to ip-address
     if (givenString.size() < index + 1)
         return ;
  
     // Select one digit and call the
     // same function for other blocks
     ipAddress = ipAddress
                 + givenString.substr(index, 1) + '.' ;
     GetAllValidIpAddress(result, givenString, index + 1, count + 1, ipAddress);
  
     // Backtrack to generate another poosible ip address
     // So we remove two index (one for the digit
     // and other for the dot) from the end
     ipAddress.erase(ipAddress.end() - 2, ipAddress.end());
  
     // Select two consecutive digits and call
     // the same function for other blocks
     if (givenString.size() < index + 2
         || givenString[index] == '0' )
         return ;
     ipAddress = ipAddress + givenString.substr(index, 2) + '.' ;
     GetAllValidIpAddress(result, givenString, index + 2, count + 1, ipAddress);
  
     // Backtrack to generate another poosible ip address
     // So we remove three index from the end
     ipAddress.erase(ipAddress.end() - 3, ipAddress.end());
  
     // Select three consecutive digits and call
     // the same function for other blocks
     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);
  
     // Backtrack to generate another poosible ip address
     // So we remove four index from the end
     ipAddress.erase(ipAddress.end() - 4, ipAddress.end());
}
  
// Driver code
int main()
{
     string givenString = "25525511135" ;
  
     // Fill result vector with all valid ip-addresses
     vector<string> result;
     GetAllValidIpAddress(result, givenString, 0, 0, "" );
  
     // Print all the generated ip-addresses
     for ( int i = 0; i < result.size(); i++) {
         cout << result[i] << "\n" ;
     }
}

Python3

# Python3 implementation of the approach 
  
# Function to get all the valid ip-addresses 
def GetAllValidIpAddress(result, givenString, index, count, ipAddress) :
  
     # If index greater than givenString size 
     # and we have four block 
     if ( len (givenString) = = index and count = = 4 ) :
  
         # Remove the last dot 
         ipAddress.pop(); 
  
         # Add ip-address to the results 
         result.append(ipAddress); 
         return ; 
  
     # To add one index to ip-address 
     if ( len (givenString) < index + 1 ) :
         return ; 
  
     # Select one digit and call the 
     # same function for other blocks 
     ipAddress = (ipAddress + 
                  givenString[index : index + 1 ] + [ '.' ]); 
      
     GetAllValidIpAddress(result, givenString, index + 1 , count + 1 , ipAddress); 
  
     # Backtrack to generate another poosible ip address 
     # So we remove two index (one for the digit 
     # and other for the dot) from the end 
     ipAddress = ipAddress[: - 2 ];
  
     # Select two consecutive digits and call 
     # the same function for other blocks 
     if ( len (givenString) < index + 2 or 
             givenString[index] = = '0' ) :
         return ; 
          
     ipAddress = ipAddress + givenString[index:index + 2 ] + [ '.' ]; 
     GetAllValidIpAddress(result, givenString, index + 2 , count + 1 , ipAddress); 
  
     # Backtrack to generate another poosible ip address 
     # So we remove three index from the end 
     ipAddress = ipAddress[: - 3 ]; 
  
     # Select three consecutive digits and call 
     # the same function for other blocks 
     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); 
  
     # Backtrack to generate another poosible ip address 
     # So we remove four index from the end 
     ipAddress = ipAddress[: - 4 ]; 
  
# Driver code 
if __name__ = = "__main__" : 
     givenString = list ( "25525511135" ); 
  
     # Fill result vector with all valid ip-addresses 
     result = [] ; 
     GetAllValidIpAddress(result, givenString, 0 , 0 , []); 
  
     # Print all the generated ip-addresses 
     for i in range ( len (result)) :
         print ("".join(result[i])); 
          
# This code is contributed by Ankitrai01

输出如下：

255.255.11.135
255.255.111.35

---