[Leetcode] Palindrome Partitioning 回文分割

leanote 發布于2019-08-14 12:32 / 2867人閱讀

摘要：深度優先搜素復雜度時間空間思路因為我們要返回所有可能的分割組合，我們必須要檢查所有的可能性，一般來說這就要使用，由于要返回路徑，仍然是典型的做法遞歸時加入一個臨時列表，先加入元素，搜索完再去掉該元素。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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