​LeetCode刷题实战131:分割回文串

程序IT圈

共 3162字,需浏览 7分钟

 ·

2020-12-21 15:09

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 分割回文串,我们先来看题面:
https://leetcode-cn.com/problems/palindrome-partitioning/

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.


A palindrome string is a string that reads the same backward as forward.

题意

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


样例

示例:

输入: "aab"
输出:
[
  ["aa","b"
],
  ["a","a","b"]
]


解题

https://www.jianshu.com/p/e1017e1674ea

这是一道很综合的题目,结合了动态规划,深度搜索和回溯法。

首先为了分割出回文串,我们首先要写出判断回文串的方法,这里使用动态规划来判断回文串,而且可以存储子串的回文串的情况。
isPalindrome[i][j]:表示i到j的子串是否是回文串。

状态转移方程:

isPalindrome[i][j] = isPalindrome[i+1][j-1] && s.charAt(i) == s.charAt(j)
自然如果一个串是回文串,那么首尾必须要相等,并且中间也是子串。
初始化,显然当i==j的时候都是回文串
当串只有两个字符且相等的时候也是回文串。

知道如何判断子串是否是回文串就好办了,然后只要模式化的深度搜索回溯即可 。

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */

    
    List> results;
    boolean[][] isPalindrome;
    
    /**
     * @param s: A string
     * @return: A list of lists of string
     */

    public List> partition(String s) {
        results = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return results;
        }
        
        getIsPalindrome(s);
        
        helper(s, 0, new ArrayList());
        
        return results;
    }
    
    private void getIsPalindrome(String s) {
        int n = s.length();
        isPalindrome = new boolean[n][n];
        
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < n - 1; i++) {
            isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }
        
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }
    }
    
    private void helper(String s,
                        int startIndex,
                        List partition
)
{
        if (startIndex == s.length()) {
            addResult(s, partition);
            return;
        }
        
        for (int i = startIndex; i < s.length(); i++) {
            if (!isPalindrome[startIndex][i]) {
                continue;
            }
            partition.add(i);
            helper(s, i + 1, partition);
            partition.remove(partition.size() - 1);
        }
    }
    
    private void addResult(String s, List partition) {
        List result = new ArrayList<>();
        int startIndex = 0;
        for (int i = 0; i < partition.size(); i++) {
            result.add(s.substring(startIndex, partition.get(i) + 1));
            startIndex = partition.get(i) + 1;
        }
        results.add(result);
    }
}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-120题汇总,希望对你有点帮助!
LeetCode刷题实战121:买卖股票的最佳时机
LeetCode刷题实战122:买卖股票的最佳时机 II
LeetCode刷题实战123:买卖股票的最佳时机 III
LeetCode刷题实战124:二叉树中的最大路径和
LeetCode刷题实战125:验证回文串
LeetCode刷题实战126:单词接龙 II
LeetCode刷题实战127:单词接龙
LeetCode刷题实战128:最长连续序列
LeetCode刷题实战129:求根到叶子节点数字之和
LeetCode刷题实战130:被围绕的区域


浏览 11
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报