回溯：分割问题

2024-03-23 20:05:40

LeetCode131. 分割回文串

https://leetcode-cn.com/problems/palindrome-partitioning/

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

回文串 是正着读和反着读都一样的字符串。

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

思路

回溯模板：

void backtracking(选择列表，路径，结果) 
{
    if (终止条件) 
    {
        存放结果;
        return;
    }

    for (在选择列表中选择) 
    {
        处理节点;
        backtracking(选择列表，路径，结果); 
        回溯，撤销处理结果
    }
}

所有用回溯解决的问题都可以抽象为树形结构：

其实切割问题也是一种组合问题。

例如对于字符串abcdef：

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

回溯三部曲：

1.递归函数的返回值和参数

定义两个全局变量，一个用来存放回文子串的path，一个用来存放所有回文子串的结果集合result。

函数里一定有一个参数：选择列表(字符串s)。

还有一个int型参数startIndex，这个参数用来记录本层递归中切割线的位置。随着递归控制树的纵向遍历，切割线向后推移(因为切割过的地方，不能重复切割)，就是要靠startIndex。

    vector<vector<string>> result;  //存放所有回文子串的结果集合
    vector<string> path;  //存放回文子串
    void backtrack(const string& s, int startIndex)

2.递归函数的终止条件

切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。

        if (startIndex == size)
        {
            result.push_back(path);
            return;
        }

3.搜索过程
我们定义的backtrack函数其实就像一个指针，在树中游走同时正确维护每个节点的属性。

        //控制树的横向遍历
        for (int i = startIndex; i < size; ++i)
        {
            if (isPalindrome(s, startIndex, i))
            {
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            }
            else
            {
                continue;
            }

            backtrack(s, i + 1);  //递归：控制树的纵向遍历
        
            path.pop_back();
        }

代码

class Solution 
{
private:
    vector<vector<string>> result;  //存放所有回文子串的结果集合
    vector<string> path;  //存放回文子串

    bool isPalindrome(const string& s, int left, int right)
    {
        while (left < right)
        {
            if (s[left] != s[right])
            {
                return false;
            }
            ++left;
            --right;
        }

        return true;
    }

    void backtrack(const string& s, int startIndex)
    {
        int size = s.size();

        if (startIndex == size)
        {
            result.push_back(path);
            return;
        }

        //控制树的横向遍历
        for (int i = startIndex; i < size; ++i)
        {
            if (isPalindrome(s, startIndex, i))
            {
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            }
            else
            {
                continue;
            }

            backtrack(s, i + 1);  //递归：控制树的纵向遍历
        
            path.pop_back();
        }
    }

public:
    vector<vector<string>> partition(string s) 
    {
        backtrack(s, 0);

        return result;
    }
};

LeetCode93. 复原IP地址

https://leetcode-cn.com/problems/restore-ip-addresses/

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。你可以按任何顺序返回答案。

有效 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 = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

思路

回溯模板：

void backtracking(选择列表，路径，结果) 
{
    if (终止条件) 
    {
        存放结果;
        return;
    }

    for (在选择列表中选择) 
    {
        处理节点;
        backtracking(选择列表，路径，结果); 
        回溯，撤销处理结果
    }
}

所有用回溯解决的问题都可以抽象为树形结构：

回溯三部曲：

1.递归函数的返回值和参数

定义一个全局变量，用来存放所有符合条件的IP地址的结果集合result。

函数里一定有一个参数：选择列表(字符串s)。

还有一个int型参数pointNum，这个参数用来记录添加逗点的数量。

    //存放所有符合条件的IP地址的结果集合
    vector<string> result;

    void backtrack(string& s, int startIndex, int pointNum)

2.递归函数的终止条件

本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。

pointNum表示逗点数量，pointNum为3说明字符串分成了4段了，然后验证一下第四段是否合法，如果合法就加入到结果集里。

        if (pointNum == 3)
        {
            if (isValid(s, startIndex, s.size() - 1))
            {
                result.push_back(s);
            }

            return;
        }

3.搜索过程
我们定义的backtrack函数其实就像一个指针，在树中游走同时正确维护每个节点的属性。

        //控制树的横向遍历
        for (int i = startIndex; i < s.size(); ++i)
        {
            if (isValid(s, startIndex, i))
            {
                s.insert(s.begin() + i + 1, '.');  //在i的后面插入一个逗点
                ++pointNum;

                //插入逗点之后下一个子串的起始位置为i + 2
                backtrack(s, i + 2, pointNum);  //递归：控制树的纵向遍历
                
                s.erase(s.begin() + i + 1);  //回溯，删除逗点
                --pointNum;
            }
            //不合法，直接结束本层循环
            else
            {
                break;
            }
        }

代码

class Solution 
{
private:
    bool isValid(const string& s, int left, int right)
    {
        if (left > right) return false;

        //0开头的数字不合法
        if (s[left] == '0' && left != right) return false;

        int num = 0;
        for (int i = left; i <= right; ++i)
        {
            num = num * 10 + s[i] - '0';
            //大于255了不合法
            if (num > 255) return false;
        }

        return true;
    }
    
    //存放所有符合条件的IP地址的结果集合
    vector<string> result;

    void backtrack(string& s, int startIndex, int pointNum)
    {
        if (pointNum == 3)
        {
            //此时startIndex有可能大于s.size() - 1
            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))
            {
                s.insert(s.begin() + i + 1, '.');  //在i的后面插入一个逗点
                ++pointNum;

                //插入逗点之后下一个子串的起始位置为i + 2
                backtrack(s, i + 2, pointNum);  //递归：控制树的纵向遍历
                
                s.erase(s.begin() + i + 1);  //回溯，删除逗点
                --pointNum;
            }
            //不合法，直接结束本层循环
            else
            {
                break;
            }
        }

    }

public:
    vector<string> restoreIpAddresses(string s) 
    {
        backtrack(s, 0, 0);

        return result;
    }
};

码农公寓

LeetCode131. 分割回文串

思路

代码

LeetCode93. 复原IP地址

思路

代码

相关文章