[LintCode] Palindrome Partitioning

NicolasHe 發(fā)布于2019-08-14 15:11 / 1170人閱讀

Problem

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

Given s = "aab", return:

[
  ["aa","b"],
  ["a","a","b"]
]

Note

backtracking, 指針溢出時(shí)添加新的結(jié)果到res集合。

Solution

public class Solution {
    public List> partition(String s) {
        // write your code here
        List> res = new ArrayList>();
        List tem = new ArrayList();
        if (s.length() == 0 || s == null){
            return res;
        }
        dfs(res, tem, s, 0);
        return res;
    }
    public void dfs(List> res, List tem, String s, int start){
        if (start == s.length()){
            res.add(new ArrayList(tem));
            return;
        }
        for (int i = start; i < s.length(); i++){
            String str = s.substring(start, i + 1);
            if (isPalindrome(str)){
                tem.add(str);
                dfs(res, tem, s, i + 1); //start+=1
                tem.remove(tem.size() - 1);
            }
        }
    }
    public boolean isPalindrome(String str){
        int l = 0;
        int r = str.length()-1;
        while (l < r){
            if (str.charAt(l) != str.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

云服務(wù)器 GPU云服務(wù)器 palindrome Partitioning -partitioning LintCode

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65433.html

相關(guān)文章

[LintCode] Palindrome Partitioning II

摘要：假設(shè)我們從后向前，分析到第位，開始判斷，若為，說明從第位向前到第位的子串是一個(gè)回文串，則就等于第位的結(jié)果加。然后讓繼續(xù)增大，判斷第位到最后一位的范圍內(nèi)，有沒有更長的回文串，更長的回文串意味著存在更小的，用新的來替換。 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
leetcode132. Palindrome Partitioning II

摘要：題目要求現(xiàn)在有一個(gè)字符串，將分割為多個(gè)子字符串從而保證每個(gè)子字符串都是回?cái)?shù)。我們只需要找到所有可以構(gòu)成回?cái)?shù)的并且得出最小值即可。即將字符作為，將字符所在的下標(biāo)列表作為。再采用上面所說的方法，利用中間結(jié)果得出最小分割次數(shù)。題目要求 Given a string s, partition s such that every substring of the partition is a ...

jeyhan 2019-08-15 14:27 評論0 收藏0
[Leetcode] Palindrome Partitioning 回文分割

摘要：深度優(yōu)先搜素復(fù)雜度時(shí)間空間思路因?yàn)槲覀円祷厮锌赡艿姆指罱M合，我們必須要檢查所有的可能性，一般來說這就要使用，由于要返回路徑，仍然是典型的做法遞歸時(shí)加入一個(gè)臨時(shí)列表，先加入元素，搜索完再去掉該元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...

leanote 2019-08-14 12:32 評論0 收藏0
[leetcode]132. Palindrome Partitioning II

摘要：用表示當(dāng)前位置最少需要切幾次使每個(gè)部分都是回文。表示到這部分是回文。如果是回文，則不需重復(fù)該部分的搜索。使用的好處就是可以的時(shí)間，也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。 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
131. Palindrome Partitioning and 140. Word Break I

摘要：找到開頭的某個(gè)進(jìn)行切割。剩下的部分就是相同的子問題。記憶化搜索，可以減少重復(fù)部分的操作，直接得到后的結(jié)果。得到的結(jié)果和這個(gè)單詞組合在一起得到結(jié)果。 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome...

stonezhu 2019-08-14 17:58 評論0 收藏0