[Leetcode] Palindrome Partitioning 回文分割

leanote 发布于2019-08-14 12:32 / 2866人阅读

摘要：深度优先搜素复杂度时间空间思路因为我们要返回所有可能的分割组合，我们必须要检查所有的可能性，一般来说这就要使用，由于要返回路径，仍然是典型的做法递归时加入一个临时列表，先加入元素，搜索完再去掉该元素。

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.
For example, given s = "aab", Return
  [
    ["aa","b"],
    ["a","a","b"]
  ]

深度优先搜素 复杂度

时间 O(N^2) 空间 O(N)

思路

因为我们要返回所有可能的分割组合，我们必须要检查所有的可能性，一般来说这就要使用DFS，由于要返回路径，仍然是典型的做法：递归时加入一个临时列表，先加入元素，搜索完再去掉该元素。对每一种可能性都调用isPalindrome函数来判断。

代码

public class Solution {
    
    List> res;
    public List> partition(String s) {
        res = new LinkedList>();
        List tmp = new LinkedList();
        helper(s, 0, tmp);
        return res;
    }
    
    private void helper(String s, int start, List tmp){
        if(start >= s.length()){
            List list = new LinkedList(tmp);
            res.add(list);
            return;
        }
        // 搜索可能的字串，如果是回文就继续搜索
        for(int i = start; i < s.length(); i++){
            String sub = s.substring(start, i+1);
            if(isPalindrome(sub)){
                tmp.add(sub);
                helper(s, i+1, tmp);
                tmp.remove(tmp.size()-1);
            }
        }
    }
    
    private boolean isPalindrome(String s){
        int i = 0, j = s.length() - 1;
        while(i

云服务器 GPU云服务器 palindrome Partitioning -partitioning LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64545.html

[leetcode]132. Palindrome Partitioning II

摘要：用表示当前位置最少需要切几次使每个部分都是回文。表示到这部分是回文。如果是回文，则不需重复该部分的搜索。使用的好处就是可以的时间，也就是判断头尾就可以确定回文。不需要依次检查中间部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...

Airy 2019-08-14 16:54 评论0 收藏0
leetcode132. Palindrome Partitioning II

摘要：题目要求现在有一个字符串，将分割为多个子字符串从而保证每个子字符串都是回数。我们只需要找到所有可以构成回数的并且得出最小值即可。即将字符作为，将字符所在的下标列表作为。再采用上面所说的方法，利用中间结果得出最小分割次数。题目要求 Given a string s, partition s such that every substring of the partition is a ...

jeyhan 2019-08-15 14:27 评论0 收藏0
[LintCode] Palindrome Partitioning II

摘要：假设我们从后向前，分析到第位，开始判断，若为，说明从第位向前到第位的子串是一个回文串，则就等于第位的结果加。然后让继续增大，判断第位到最后一位的范围内，有没有更长的回文串，更长的回文串意味着存在更小的，用新的来替换。 Problem Given a string s, cut s into some substrings such that every substring is a p...

funnyZhang 2019-08-14 15:30 评论0 收藏0
LeetCode - 009 - 回文数（palindrome-number）

摘要：最后，我们判断一开始的两种情况，并返回或者即可。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-05-22 19:30:42 Recently revised in 2019-05-23 11:42:52 一目录不折腾的前端，和咸鱼有什么区别目录一目录二前言三解题 3.1 解题 - 数组操作 ...

hikui 2019-05-23 16:23 评论0 收藏0
[Leetcode] Palindrome Permutation 回文变换

摘要：最笨的方法就是用的解法，找出所有的，然后再用中判断回文的方法来判断结果中是否有回文。而中心对称点如果是字符，该字符会是奇数次，如果在两个字符之间，则所有字符都是出现偶数次。 Palindrome Permutation Given a string, determine if a permutation of the string could form a palindrome. F...

svtter 2019-08-14 12:36 评论0 收藏0