算法练习第23天|131.分割回文串、93.复原IP地址

131.分割回文串

131. 分割回文串 - 力扣（LeetCode）https://leetcode.cn/problems/palindrome-partitioning/description/

题目描述：

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文串是向前和向后读都相同的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

思路分析：

本题的两个难点：

1. 字符串的切割方式

2. 回文串的判断

其实回文串的判断还是比较简单的，只需要双指针法就可以实现：

    //双指针法
    bool isHuiwen(const string& s, int start, int end){
        while(start < end){
            if(s[start] != s[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

判断回文的函数有三个参数，字符串本身s，字符串起始位置start以及字符串末尾位置（最后一个字符的位置）。这些位置其实就是下标。

比较难的是我们如何切割得到子串。

我们在前面的文章中讲到，如果从一个集合中取组合就需要使用startIndex（见这篇博文39题的思路分析部分）。算法练习第22天|39. 组合总和、40.组合总和II-CSDN博客https://blog.csdn.net/Brillian123/article/details/138899798同时还会用下面这样的for循环来遍历集合中的元素：

for(int i = startIndex; i<s.size(); i++){}

其实本题的切割问题也可以看作前面题目中从集合中取元素的问题。

例如对于字符串abcdef：

组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。

区别就在于切割需要我们想办法通过一个区间将子串提取出来。startIndex初始值为0，所以其最开始会位于字符串的最左端。而在横向遍历时，i是会变的，【startIndex，i】区间就是子串。在提取子串的时候，i-startIndex+1就是子串的长度。当回溯进行到startIndex已经到达字符串末尾时，表明分割的子串一直满足条件。下面时按照往常的回溯三部曲而写的代码，但是不是很好理解。不理解的小伙伴可以直接跳过。

解法一：

class Solution {
    //双指针法
    bool isHuiwen(const string& s, int start, int end){
        while(start < end){
            if(s[start] != s[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
public:
    vector<string> path;
    vector<vector<string>> result;

    //回溯第一步：确认回溯函数返回值及参数
    void backTracking(string& s, int startIndex){
        //回溯第二步：确认回溯终止条件
        //当切割线走到字符串末尾，说明切割出来的子串是符号条件的，result做记录
        if(startIndex == s.size()){
            result.push_back(path);
            return;
        }
        //入股切割线不在字符串的末尾，说明分割还未进行彻底，需要判断【startIndex，i】的子串
        for(int i = startIndex; i<s.size(); i++){
            if(isHuiwen(s, startIndex, i)){
                string str = s.substr(startIndex,i-startIndex+1);
                path.push_back(str);
                backTracking(s,i+1);
                path.pop_back();
            }
            else{
                continue;
            }
            
        }
    }
    vector<vector<string>> partition(string s) {
        backTracking(s, 0);
        return result;
    }
};

解法二（比较容易理解）：

先介绍一下力扣负雪明烛的回溯模板，此题用这个模板更容易理解。

vector<string> path;
vector<vector<string>> result;

void backtrack(未探索区域, result, path){
    if (未探索区域满足结束条件){
        result.push_back(path) # 深度拷贝
        return;
    }
    for (未探索区域当前可能的选择){
        if (当前选择符合要求){
            path.add(当前选择);
            backtrack(新的未探索区域, res, path);
            path.pop_back();
        }
    }
}
作者：负雪明烛
链接：https://leetcode.cn/problems/palindrome-partitioning/solutions/640028/hui-su-fa-si-lu-yu-mo-ban-by-fuxuemingzh-azhz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本题需要我们把字符串分成一系列的回文子串，按照模板，我们的思路应该是这样的：

未探索区域：剩余的未搜索的字符串 s；
结束条件：s 为空；
未探索区域当前可能的选择：每次选择可以选取s的前若干个字符组成的子串str：s[1...i]；
当前选择符合要求：子串str 是回文字符串；
新的未探索区域：s 去除掉子串str后剩余的部分，s[i+1...N]。

对应的树形结构如下图所示：

观察上图可知，回溯结束的标志就是未探索区域为空【】,所以可以得到下面的代码：

回溯函数除了参数除了需要字符串，还用到了老朋友result和path（也可以去掉，因为是全局的）。终止条件就是当未探索区域为空时，result记录path然后return。需要注意的是，只有在当前子串为回文串时才会发生递归，非探索区域才会进一步缩小。

    vector<string> path;
    vector<vector<string>> result;    
//新模板回溯第一步：确认回溯函数返回值及参数
    void backTracking(string s, vector<vector<string>>& result, vector<string>&  path){
        //回溯第二步：确认回溯终止条件
        //当未探索区域s为空时，说明回溯全部搜索完毕
        if(s.empty()){
            result.push_back(path);
            return;
        }
    }

回溯第三步就是提取未探索区域的子串，然后判断子串是否为回文串，如果是，path记录，然后未探索区域进一步缩小，进行递归，回溯。

        //回溯第三步：开始找未探索区域的子串
        for(int i = 1; i <= s.size(); i++){
            //s从0位置开始的后面的i个元素作为子串,区间【0，i-1】
            string str = s.substr(0,i);  
            
            if(isHuiwen(str, 0, str.size()-1)){
                path.push_back(str);  //记录
                backTracking(s.substr(i), result, path);  //递归
                path.pop_back();  //回溯
            }
        }

整体代码如下：

class Solution {
    //双指针法
    bool isHuiwen(const string s, int start, int end){    
        while(start < end){
            if(s[start] != s[end]){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
public:
    vector<string> path;
    vector<vector<string>> result;

    //新模板回溯第一步：确认回溯函数返回值及参数
    void backTracking(string s, vector<vector<string>>& result, vector<string>&  path){
        //回溯第二步：确认回溯终止条件
        //当未探索区域s为空时，说明回溯全部搜索完毕
        if(s.empty()){
            result.push_back(path);
            return;
        }
        //回溯第三步：开始找未探索区域的子串
        for(int i = 1; i <= s.size(); i++){
            //s从0位置开始的后面的i个元素作为子串,区间【0，i-1】
            string str = s.substr(0,i);  
            
            if(isHuiwen(str, 0, str.size()-1)){
                path.push_back(str);  //记录
                backTracking(s.substr(i), result, path);  //递归
                path.pop_back();  //回溯
            }
        }                
        
    }
    vector<vector<string>> partition(string s) {
        backTracking(s, result, path);
        return result;
    }
};

93.复原IP地址

93. 复原 IP 地址 - 力扣（LeetCode）https://leetcode.cn/problems/restore-ip-addresses/description/

题目描述：

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

思路分析：

class Solution {
public:
    vector<string> result;
    vector<int> path;//当前分割好的可以作为ip地址一个段的数字
    //原始字符串s、开始搜索的下标startIndex, 段数idx（正确的ip地址一共有4段组成）
    void backTracking(string& s, int startIndex, int idx){
        //回溯终止条件：startIndex到达字符串末尾，且此时idx为4段
        if(startIndex == s.size() && idx == 4){
           string ip = to_string(path[0]);
           for(int i = 1;  i < path.size(); i++) {
                ip = ip + '.' + to_string(path[i]); 
           }
           result.push_back(ip);
           return;
        }
        if(idx>4) return;

        //从startIndex开始找
        for(int i = startIndex, num=0; i<s.size();i++){
            num = num*10 + (s[i]-'0');
            if(num > 255 ) break;
            //只要不超过255，就算满足一个段的要求，path记录
            path.push_back(num);  
            //递归，从下一个位置开始接着找，要找的是下一个段的
            backTracking(s, i+1, idx+1);
            path.pop_back();

            //最后这一句是排除前导0。
            if(num == 0) break;  
        }

    }


    vector<string> restoreIpAddresses(string s) {
        backTracking(s,0,0);
        return result;
    }
};

class Solution {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法，直接结束本层循环
        }
    }
    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};