leetcode 131. Palindrome Partitioning 按照index做DFS深度优先遍历-蒲公英云

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

Bertha 。 2022-06-08 05:36 256阅读 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 去除一个字符的回文字符串判断 + 双指针一起学习

代码如下：

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;
    }
};