Dynamic programming problem (6)

One 、 The number string is converted into IP Address

Solution 1 : enumeration ( recommend )

about IP character string , If there are only numbers , Is equivalent to the need for us to IP Three points of the address are inserted into the string , The position of the first point can only be in the first character 、 Second character 、 After the third character , The second point can only be after the first point 1-3 Within four positions , The third point can only be after the second point 1-3 Within four positions , And the number after the third point shall not exceed 3, because IP Each address has a maximum of 3 Digit number .

• Enumerate the positions of these three points in turn .
• Then cut out four numbers .
• Compare the intercepted figures , Not greater than 255, Besides 0 There can be no leading 0, Then it can be assembled into IP Add the address to the answer .

class Solution {
    
public:
    vector<string> restoreIpAddresses(string s) {
    
        vector<string> res;
        int n = s.length();
        // Traverse IP Possible location of the point （ The first point ）
        for(int i = 1; i < 4 && i < n - 2; i++){
     
            // The position of the second point 
            for(int j = i + 1; j < i + 4 && j < n - 1; j++){
     
                // The position of the third point 
                for(int k = j + 1; k < j + 4 && k < n; k++){
    
                    // The remaining number in the last paragraph cannot exceed 3
                    if(n - k >= 4) 
                        continue; 
                    // Segment from the position of the point 
                    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 Each number is not greater than 255
                    if(stoi(a) > 255 || stoi(b) > 255 || stoi(c) > 255 || stoi(d) > 255) 
                        continue;
                    // Exclude leading 0 The situation of 
                    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;
                    // assemble IP Address 
                    string temp = a + "." + b + "." + c + "." + d; 
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
};

Time complexity ： If you will 3 As a constant , The complexity is O(1), If you will 3 As string length 1/4, The complexity is O(n^3), Three nested loops
Spatial complexity ： If you will 3 As a constant , The complexity is O(1), If you will 3 As string length 1/4, The complexity is O(n),4 A temporary variable that records the intercepted string .res It belongs to returning the necessary space .

Solution 2 : recursive + to flash back

about IP The address takes out one number and one dot at a time , The rest can be considered as a sub problem , So you can use recursion and backtracking to insert points into numbers .

• Use step Record the number of numbers divided ,index Record the subscript of recursion , Ending recursion means step Have been to 4, And the subscript reaches the end of the string .
• In body recursion , Add one character at a time as a number , You can add up to three numbers , The remaining string enters recursively to construct the next number .
• Then check whether each number is legal （ No more than 255 And there is no leading 0）.
• legal IP It needs to be connected , At the same time, you need to backtrack after this round of recursion .

class Solution {
    
private: 
    // Return to the answer 
    vector<string> res; 
    // Record input string 
    string s; 
    // Record segmentation IP Numeric string 
    string nums; 
public:
    //step Indicates the number of digits ,index Indicates a string subscript 
    void dfs(int step, int index){
     
        // The currently split string 
        string cur = ""; 
        // Four numbers are separated 
        if(step == 4){
     
            // The subscript must go to the end 
            if(index != s.length()) 
                return;
            res.push_back(nums);
        }else{
    
            // Longest traversal 3 position 
            for(int i = index; i < index + 3 && i < s.length(); i++){
     
                cur += s[i];
                // Turn to number comparison 
                int num = stoi(cur); 
                string temp = nums;
                // No more than 255 And there should be no leading 0
                if(num <= 255 && (cur.length() == 1 || cur[0] != '0')){
     
                    // Add some 
                    if(step - 3 != 0) 
                        nums += cur + ".";
                    else
                        nums += cur;
                    // Recursively find the next number 
                    dfs(step + 1, i + 1); 
                    // to flash back 
                    nums = temp; 
                }
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
    
        this->s = s;
        dfs(0, 0);
        return res;
    }
};

Time complexity ：O(3^n),3 Branch tree recursion
Spatial complexity ：O(n), The recursive stack depth is n

Two 、 Edit distance ( One )

solution : Dynamic programming

Change the first string into the second string , We need to turn the substring of the first string into the second string one by one with the least operation , This involves increasing the length of the first string , State shift , Then consider dynamic programming . use dp[i][j] Indicates that from the beginning of two strings to str1[i] and str2[j] Edit distance required for substring up to , That's obvious dp[str1.length][str2.length] Is the editing distance we require .（ Subscript from 1 Start ）

• Suppose the second string is empty , It is obvious that every additional character in the first string substring , Edit the distance by adding 1, This step is to delete ; Empathy , Suppose the first string is empty , Every additional character in the second string , The writer's distance increases 1, This step is to add .
• The state transition is definitely going to dp The matrix is filled with , Then go through each length of the first string , Corresponds to each length of the second string . If you traverse to str1[i] and str2[j] The location of , The two characters are the same , There is no need to operate the extra characters , The number of operations is the same as the previous one of the two substrings , So there is dp[i][j]=dp[i−1][j−1]; If the two characters are different , Then these two characters need to be edited , But the shortest distance at this time is not necessarily to modify the last bit , It is also possible to delete a character or add a character , Therefore, we choose the minimum value of the three cases to increase the editing distance , namely 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] To str1[i] and str2[j] Edit distance required for substring up to 
        vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1, 0)); 
        // Initialize boundary 
        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;
        // Traverse every position of the first string 
        for(int i = 1; i <= n1; i++) 
            // Corresponding to each position of the second string 
            for(int j = 1; j <= n2; j++){
     
                // If the characters are the same , There is no need to edit here 
                if(str1[i - 1] == str2[j - 1]) 
                    // Directly equal to the distance between the former one 
                    dp[i][j] = dp[i - 1][j - 1]; 
                else
                    // Select the minimum distance plus the edit distance here 1
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1; 
            }
        return dp[n1][n2]; 
    }
};

Time complexity ：O(mn), among m、n Is the length of two strings , initialization dp Array traverses two strings separately , The follow-up dynamic planning process traverses two levels
Spatial complexity ：o(mn), Auxiliary array dp Space