LeetCode算法编程 - Palindrome Partitioning

1、题目

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

题目解释:

指定字符串 s,返回 s 所有可能的子串,每个子串必须是一个回文(指顺读和倒读都一样的字符串),示例如上图。

 

分析

仔细思考一下问题,会发现题目的做法是遍历所有的可能,找出合适的解。大家可以先尝试下自已写这个算法,这道题会考验递归的基本功。

 

先介绍下回溯算法,回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:

1、定义一个解空间,它包含问题的解。

2、利用适于搜索的方法组织解空间。

3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。

 

源码:

class Solution {
public:

    // 检查一个字符串是否为回文
    bool check_palindrome(string s)
    {
        int size = s.size();
        for (int i = 0; i < size/2; i ++)
        {
            if (s[i] != s[size - i - 1])
            {
                return false;
            }
        }

        return true;
    }

    void find_partition_sln(string s, 
                            vector<string> &sln, 
                            vector<vector<string> > &result)
    {
        // 边界结束条件
        if (s.size() == 0)
        {
            // 能到这,说明找到了一个可能的解,前面的子串都是符合条件的
            result.push_back(sln);
        }

        int size = s.size();

        // 把字符串从第一个位置到最后一个位置,依次进行分隔
        // 并在每一种情况下,利用深度搜索找到合适的解
        for (int i = 1; i <= size; i ++)
        {
            string front;
            string remain;

            front.assign(s, 0, i);
            remain.assign(s, i, size - i);

            if (check_palindrome(front))
            {
                // front符合条件
                sln.push_back(front);

                // 寻找以front开头的可行解,深度优先
                find_partition_sln(remain, sln, result);

                // 重新开始下一个查找
                sln.pop_back();
            }
        }
    }

    vector<vector<string> > partition(string s) {

        vector<string> sln;
        vector<vector<string> > result;
        
        find_partition_sln(s, sln, result);

        return result;
    }
};

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。