leetcode 131. Palindrome Partitioning 按照index做DFS深度优先遍历

Bertha 。 2022-06-08 05:36 157阅读 0赞

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”\]  
\]

本题是找到所有的回文子串，就是按照index做一下深度优先遍历，但是注意剪枝。

这道题最直接的方法就是寻找到所有的子串组合，然后判断是否是满足回文要求，所以直接DFS深度优先遍历找到所有的可能即可，不需要想的太复杂，这是一道很经典的按照index的DFS即可

建议和[leetcode 680. Valid Palindrome II 去除一个字符的回文字符串判断 + 双指针][leetcode 680. Valid Palindrome II _ _] 一起学习

代码如下：

import java.util.ArrayList;
    import java.util.List;
    
    /* 
     * 本题考查回溯算法。从下标0开始遍历字符串，一旦在下标 i 找到回文子字符串，
     * 那么就把下标从 0 到 i 的子字符串加入temp中，继续从下标 i 接着往下找，一旦
     * curIndex等于字符串长度，那么就把temp加入到result中。如果一直到最后都没找到
     * 回文子字符串，那么就进行剪枝：
     * 
     *  这个题值得反思回溯算法, 需要好好的想一下
     * */
    public class Solution 
    {
        List<List<String>> res = new ArrayList<>();
        public List<List<String>> partition(String s) 
        {
            if(s==null || s.length()<=0 )
                return res;
            List<String> one = new ArrayList<>();
            dfs(one,s,0);
            return res;
        }
    
        public void dfs(List<String> one, String s, int index) 
        {
            if(index == s.length())
            {
                res.add(new ArrayList<>(one));
                return ;
            }else
            {
                for(int i=index+1;i<=s.length();i++)
                {
                    String tmp = s.substring(index,i);
                    if(isPalindrome(tmp))
                    {
                        one.add(tmp);
                        dfs(one, s, i);
                        one.remove(one.size()-1);
                    }
                }
            }
        }
        private boolean isPalindrome(String s)
        {
            int begin=0,end=s.length()-1;
            while(begin<end)
            {
                if(s.charAt(begin)!=s.charAt(end))
                    return false;
                begin++;
                end--;
            }
            return true;
        }
    }

下面是C++的做法，就是做一个DFS深度优先遍历即可完成

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<vector<string>> res;
        vector<vector<string>> partition(string s) 
        {
            vector<string> one;
            getAll(s, 0, one);
            return res;
        }
    
        void getAll(string s,int index,vector<string>& one)
        {
            if (index >= s.length())
            {
                res.push_back(one);
                return;
            }
            else
            {
                for (int len = 1; len + index <= s.length(); len++)
                {
                    string tmp = s.substr(index, len);
                    if (isVaild(tmp))
                    {
                        one.push_back(tmp);
                        getAll(s, index + len, one);
                        one.erase(one.end() - 1);
                    }
                }
            }
        }
    
        bool isVaild(string s)
        {
            int i = 0,j = s.length() - 1;
            while (i < j)
            {
                if (s[i] != s[j])
                    return false;
                else
                {
                    i++;
                    j--;
                }
            }
            return true;
        }
    };

[leetcode 680. Valid Palindrome II _ _]: http://blog.csdn.net/jackzhang_123/article/details/78880022