讨论/《算法面试题汇总》 - 分割回文串/
《算法面试题汇总》 - 分割回文串
共 7 个回复

打卡!!

DP解法思路:
首先回文串有天然的动态转移优势,下面先说一下回文串的动态转移优势在哪里?
回文串有如下性质:
回文串首字符和尾字符不相等,则该串必然不是回文串;
回文串首字符和尾字符相等,则该串是否为回文串由除去首字符和尾字符的子串决定;
不妨设dp(i,j)表示字符串i-j之间字符是否尾回文串,则有如下结论成立
j-i<=2时 dp(i,j)=s[i]==s[j]
j-i>2时 dp(i,j)=s[i]==s[j]&&dp(i+1,j-1)

DPTable只是用来记录某个区间子串是否为回文串,剩下的问题可以这么来思考:
假设一颗N叉树,根节点是满足回文条件的s的前缀子串(a,aa),保证该树中每个节点都是回文串,且从根节点到叶子节点路径上的所有子串连接起来后正好为串s;
因此基本转化为这样一颗N叉树的所有路径问题了;
代码如下:

 //结果集
    List<List<String>> res = new ArrayList<>();
    //当前路径
    List<String> path = new ArrayList<>();
    //回文串判断表 isPalindrome[i][j]=s[i...j]
    boolean[][] isPalindrome;

    public List<List<String>> partition(String s) {
        int len = s.length();
        char[] arr = s.toCharArray();
        isPalindrome = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            isPalindrome[i][i] = true;
        }
        //回文状态转移dp[i][j]=arr[i]==arr[j]&&dp[i+1][j-1]
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (j - i < 3) {
                    isPalindrome[i][j] = arr[i] == arr[j];
                } else {
                    isPalindrome[i][j] = arr[i] == arr[j] && isPalindrome[i + 1][j - 1];
                }
            }
        }
        //深度优先搜索
        DFS(s, 0, s.length() - 1, isPalindrome);
        return res;
    }

    //N叉树深度优先搜索
    private void DFS(String s, int start, int end, boolean[][] isPalindrome) {
        if (start > end) {
            List<String> l = new ArrayList<>();
            l.addAll(path);
            res.add(l);
            return;
        }
        //N叉树分支遍历
        for (int len = 1; len <= end - start + 1; len++) {

            if (!isPalindrome[start][start + len - 1]) continue;
            //路径添加本分段
            path.add(s.substring(start, start + len));
            //下层继续深度优先搜索
            DFS(s, start + len, end, isPalindrome);
            //路径删除本分段
            path.remove(path.size() - 1);
        }
    }

思路非本人原创,之前做了最长回文子串此题,大部分思路都源于官方解答,然后添加自己的理解!!

1
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """

        def check(left, right):
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True

        def dfs(start, path):

            if start == len(s):
                res.append(path.copy())
                return

            for i in range(start, len(s)):

                if not check(start, i):
                    continue

                path.append(s[start:i + 1])
                dfs(i + 1, path)
                path.pop(-1)

        res = []
        dfs(0, [])
        return res
1

aab的划分为什么不能是a aa a b呢,一定要是a a b aa b吗

class Solution:

def partition(self, s: str) -> List[List[str]]:
    result=[]
    store=[]
    n=len(s)
    def isPalindrome(s_cut):
        return s_cut[::-1]==s_cut
    for i in range(1,n+1):
        for j in range(n+1-i):
            if (s[j:j+i] not  in store) and isPalindrome(s[j:j+i]):
                store.append(s[j:j+i])
    def dfs(start,path):
        if start==n:
            result.append(path[:])
            return
        for i in range(start+1,n+1):
            if s[start:i] in store:
                path.append(s[start:i])
            else:
                continue
            dfs(i,path)
            path.pop(-1)
    dfs(0,[])
    return result
深度搜索 我看没有C++的解法 就贴上了 性能不是很好
class Solution {
public:
    vector<vector<string>> ret;
    vector<vector<string>> partition(string s) {
        vector<string> tmpRet;
        myHelp(s, tmpRet, 0);
        return ret;

    }
    bool myCheck(string s, int start, int end){
        for(int i = start; i <= (start + end) / 2; i++){
            if(s[i] != s[start + end - i]){
                return false;
            }
        }
        return true;
    }
    void myHelp(string s, vector<string> tmpRet, int start){
        if(start > s.size() - 1){
            ret.push_back(tmpRet);
            return ;
        }
        for(int i = start;i < s.size(); i++){
            if(myCheck(s, start, i)){
                tmpRet.push_back(s.substr(start, i - start + 1));
//                cout<<"cat: "<<s.substr(start, i - start + 1)<<endl;
                myHelp(s, tmpRet, i + 1);
                tmpRet.pop_back();
            }
        }

    }
};
class Solution(object):
    def partition(self, s):
        self.isPalindrome = lambda s : s == s[::-1]
        res = []
        self.backtrack(s, res, [])
        return res
        
    def backtrack(self, s, res, path):
        if not s:
            res.append(path)
            return
        for i in range(1, len(s) + 1): #注意起始和结束位置
            if self.isPalindrome(s[:i]):
                self.backtrack(s[i:], res, path + [s[:i]])

回溯算法的正确使用方式