C++实现：递归与非递归方法解析IPv4地址恢复

在本篇代码中，主要讨论的是如何利用C++编程语言实现LeetCode上的一个问题——**恢复IP地址**（Restore IP Addresses）。问题描述是，给定一个只包含数字的字符串，例如 "25525511135"，目标是通过重新排列这些数字，生成所有可能的IPv4地址格式，如 "255.255.11.135" 或 "255.255.111.35"。 该问题涉及到两个主要的方法来解决，一个是递归方法，另一个是非递归方法。 ### 递归写法： 递归函数`helper`是核心部分，它采用分治策略来逐步构建IP地址。函数接收五个参数：一个结果存储向量`vs`、原始字符串`s`、当前构建的IP地址`cur_str`、当前处理的字符串索引`str_idx`以及已使用的地址部分计数`count`。递归的基本条件是当`count`达到4且`str_idx`等于字符串结束时，将`cur_str`添加到结果列表中。 函数首先检查剩余字符是否足够构建下一个子地址（长度1到3），然后处理边界情况，比如字符串过短或第一个数字是0。如果子字符串表示的整数大于255，则跳过当前尝试。如果`count`为3，表示已经找到了3个部分，直接调用`helper`继续递归；否则，需要在子字符串末尾加上"."。 ### 非递归写法： 非递归版本同样实现了同样的逻辑，但采用了迭代的方式。它在`restoreIpAddresses`公共函数中调用`helper`，并维护一个结果列表`vs`。在遍历输入字符串的过程中，逐个检查子字符串，并根据规则决定是递归处理还是结束当前子路径。这种方法避免了递归带来的栈空间开销，适用于较大的输入字符串。 这个代码实现了一个高效的算法来解决LeetCode的恢复IP地址问题，利用C++的控制结构和字符串操作，确保每个生成的IP地址都是有效的，并且满足IPv4地址的规范。理解递归和非递归的实现方式有助于深入理解这个问题以及在其他相似场景中的解决方案。同时，注意在实际应用中，对于大范围输入，性能优化和错误处理也是必不可少的。