一、数字字符串转化成IP地址

解法一:枚举(推荐)

对于IP字符串，如果只有数字，则相当于需要我们将IP地址的三个点插入字符串中，而第一个点的位置只能在第一个字符、第二个字符、第三个字符之后，而第二个点只能在第一个点后1-3个位置之内，第三个点只能在第二个点后1-3个位置之内，且要要求第三个点后的数字数量不能超过3，因为IP地址每位最多3位数字。

• 依次枚举这三个点的位置。
• 然后截取出四段数字。
• 比较截取出来的数字，不能大于255，且除了0以外不能有前导0，然后才能组装成IP地址加入答案中。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        int n = s.length();
        //遍历IP的点可能的位置（第一个点）
        for(int i = 1; i < 4 && i < n - 2; i++){ 
            //第二个点的位置
            for(int j = i + 1; j < i + 4 && j < n - 1; j++){ 
                //第三个点的位置
                for(int k = j + 1; k < j + 4 && k < n; k++){
                    //最后一段剩余数字不能超过3
                    if(n - k >= 4) 
                        continue; 
                    //从点的位置分段截取
                    string a = s.substr(0, i);
                    string b = s.substr(i, j - i);
                    string c = s.substr(j, k - j);
                    string d = s.substr(k);
                    //IP每个数字不大于255
                    if(stoi(a) > 255 || stoi(b) > 255 || stoi(c) > 255 || stoi(d) > 255) 
                        continue;
                    //排除前导0的情况
                    if((a.length() != 1 && a[0] == '0') || (b.length() != 1 && b[0] == '0') ||  (c.length() != 1 && c[0] == '0') || (d.length() != 1 && d[0] == '0'))
                        continue;
                    //组装IP地址
                    string temp = a + "." + b + "." + c + "." + d; 
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

时间复杂度：如果将3看成常数，则复杂度为O(1)，如果将3看成字符串长度的1/4，则复杂度为O(n^3)，三次嵌套循环
空间复杂度：如果将3看成常数，则复杂度为O(1)，如果将3看成字符串长度的1/4，则复杂度为O(n)，4个记录截取字符串的临时变量。res属于返回必要空间。

解法二:递归+回溯

对于IP地址每次取出一个数字和一个点后，对于剩余的部分可以看成是一个子问题，因此可以使用递归和回溯将点插入数字中。

• 使用step记录分割出的数字个数，index记录递归的下标，结束递归是指step已经为4，且下标到达字符串末尾。
• 在主体递归中，每次加入一个字符当数字，最多可以加入三个数字，剩余字符串进入递归构造下一个数字。
• 然后要检查每次的数字是否合法（不超过255且没有前导0）.
• 合法IP需要将其连接，同时递归完这一轮后需要回溯。

class Solution {
private: 
    //返回答案
    vector<string> res; 
    //记录输入字符串
    string s; 
    //记录分段IP数字字符串
    string nums; 
public:
    //step表示第几个数字，index表示字符串下标
    void dfs(int step, int index){ 
        //当前分割出的字符串
        string cur = ""; 
        //分割出了四个数字
        if(step == 4){ 
            //下标必须走到末尾
            if(index != s.length()) 
                return;
            res.push_back(nums);
        }else{
            //最长遍历3位
            for(int i = index; i < index + 3 && i < s.length(); i++){ 
                cur += s[i];
                //转数字比较
                int num = stoi(cur); 
                string temp = nums;
                //不能超过255且不能有前导0
                if(num <= 255 && (cur.length() == 1 || cur[0] != '0')){ 
                    //添加点
                    if(step - 3 != 0) 
                        nums += cur + ".";
                    else
                        nums += cur;
                    //递归查找下一个数字
                    dfs(step + 1, i + 1); 
                    //回溯
                    nums = temp; 
                }
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        this->s = s;
        dfs(0, 0);
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

时间复杂度：O(3^n)，3个分枝的树型递归
空间复杂度：O(n)，递归栈深度为n

二、 编辑距离(一)

解法:动态规划

把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转移，那可以考虑动态规划。用dp[i][j]表示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的编辑距离，那很明显dp[str1.length][str2.length]就是我们要求的编辑距离。（下标从1开始）

• 假设第二个字符串为空，那很明显第一个字符串子串每增加一个字符，编辑距离就加1，这步操作是删除；同理，假设第一个字符串为空，那第二个字符串每增加一个字符，编剧距离就加1，这步操作是添加。
• 状态转移肯定是将dp矩阵填满，那就遍历第一个字符串的每个长度，对应第二个字符串的每个长度。如果遍历到str1[i]和 str2[j]的位置，这两个字符相同，这多出来的字符就不用操作，操作次数与两个子串的前一个相同，因此有dp[i][j]=dp[i−1][j−1]；如果这两个字符不相同，那么这两个字符需要编辑，但是此时的最短的距离不一定是修改这最后一位，也有可能是删除某个字符或者增加某个字符，因此我们选取这三种情况的最小值增加一个编辑距离，即dp[i][j]=min(dp[i−1][j−1],min(dp[i−1][j],dp[i][j−1]))+1。
  

class Solution {
public:
    int editDistance(string str1, string str2) {
        int n1 = str1.length();
        int n2 = str2.length();
        //dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
        vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1, 0)); 
        //初始化边界
        for(int i = 1; i <= n1; i++) 
            dp[i][0] = dp[i - 1][0] + 1;
        for(int i = 1; i <= n2; i++)
            dp[0][i] = dp[0][i - 1] + 1;
        //遍历第一个字符串的每个位置
        for(int i = 1; i <= n1; i++) 
            //对应第二个字符串每个位置
            for(int j = 1; j <= n2; j++){ 
                //若是字符相同，此处不用编辑
                if(str1[i - 1] == str2[j - 1]) 
                    //直接等于二者前一个的距离
                    dp[i][j] = dp[i - 1][j - 1]; 
                else
                    //选取最小的距离加上此处编辑距离1
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; 
            }
        return dp[n1][n2]; 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度：O(mn)，其中m、n分别为两个字符串的长度，初始化dp数组单独遍历两个字符串，后续动态规划过程两层遍历
空间复杂度：o(mn)，辅助数组dp的空间