力扣--动态规划/深度优先算法/回溯算法93.复原IP地址

这题主要用了动态规划和回溯算法。

1. 动态规划数组初始化（DP数组）:

   • 首先，创建一个二维数组dp，用于记录字符串中哪些部分是合法的IP地址。
   • 对字符串进行遍历，同时考虑每个可能的IP地址部分（每部分由1到3个字符组成，对应0-255），并根据IPv4地址的规则进行判断，更新dp数组。

2. 深度优先搜索（DFS）:

   • 定义DFS函数，用于递归生成合法的IPv4地址。该函数采用回溯法，遍历每一部分可能的范围，将符合条件的部分添加到当前路径中。
   • 如果已经形成四个部分且遍历到字符串末尾，将路径转为字符串，并加入结果集。
   • 否则，继续递归生成下一部分。
   • 在生成下一部分之前，将路径中的当前部分标记为一个点号（'.'），以区分IPv4地址的各个部分。

3. 返回结果:

   • 在主函数restoreIpAddresses中，首先初始化dp数组，然后调用DFS函数，开始生成合法的IPv4地址。
   • 最后，返回生成的IPv4地址结果集。

class Solution {vector<string> result;  // 存储结果的容器vector<char> path;      // 存储当前路径的容器// 深度优先搜索函数，用于生成合法的IPv4地址void dfs(vector<vector<bool>>& dp, string s, int start, int num) {num++;if (num >= 5)  // 如果已经有四个部分了，结束递归return;// 遍历当前部分的可能范围for (int i = start; i - start <= 2 && i < s.size(); i++) {if (dp[start][i] == true) {// 将当前部分加入路径for (int j = start; j <= i; j++)path.push_back(s[j]);// 如果已经是最后一部分且遍历到字符串末尾，将路径转为字符串加入结果集if (i == s.size() - 1 && num == 4) {string str;str.assign(path.begin(), path.end());result.push_back(str);}// 否则，继续递归生成下一部分else {path.push_back('.');dfs(dp, s, i + 1, num);path.pop_back();}// 回溯，将当前部分从路径中移除for (int j = start; j <= i; j++)path.pop_back();}}return;}public:// 主函数，生成合法IPv4地址的入口vector<string> restoreIpAddresses(string s) {int n = s.size();// dp数组用于记录字符串中哪些部分是合法的vector<vector<bool>> dp(n, vector<bool>(n, false));// 遍历字符串，初始化dp数组for (int i = 0; i < n; i++) {for (int j = i; j <= i + 2 && j < n; j++) {if (i == j)dp[i][j] = true;else if (i == j - 1) {if (s[i] == '0')dp[i][j] = false;elsedp[i][j] = true;} else {if (s[i] == '0' || s[i] >= '3')dp[i][j] = false;else if (s[i] == '1')dp[i][j] = true;else {if (s[i + 1] <= '4' || (s[i + 1] == '5' && s[j] <= '5'))dp[i][j] = true;}}}}// 调用深度优先搜索函数，开始生成合法IPv4地址dfs(dp, s, 0, 0);// 返回最终结果return result;}
};