Problem
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
ExampleGiven s = "aab", return: [ ["aa","b"], ["a","a","b"] ]Note
backtracking, 指針溢出時添加新的結果到res集合。
Solutionpublic 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; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/65433.html
摘要:假設我們從后向前,分析到第位,開始判斷,若為,說明從第位向前到第位的子串是一個回文串,則就等于第位的結果加。然后讓繼續增大,判斷第位到最后一位的范圍內,有沒有更長的回文串,更長的回文串意味著存在更小的,用新的來替換。 Problem Given a string s, cut s into some substrings such that every substring is a p...
摘要:題目要求現在有一個字符串,將分割為多個子字符串從而保證每個子字符串都是回數。我們只需要找到所有可以構成回數的并且得出最小值即可。即將字符作為,將字符所在的下標列表作為。再采用上面所說的方法,利用中間結果得出最小分割次數。 題目要求 Given a string s, partition s such that every substring of the partition is a ...
摘要:深度優先搜素復雜度時間空間思路因為我們要返回所有可能的分割組合,我們必須要檢查所有的可能性,一般來說這就要使用,由于要返回路徑,仍然是典型的做法遞歸時加入一個臨時列表,先加入元素,搜索完再去掉該元素。 Palindrome Partitioning Given a string s, partition s such that every substring of the parti...
摘要:用表示當前位置最少需要切幾次使每個部分都是回文。表示到這部分是回文。如果是回文,則不需重復該部分的搜索。使用的好處就是可以的時間,也就是判斷頭尾就可以確定回文。不需要依次檢查中間部分。 Given a string s, partition s such that every substring of the partition is a palindrome. Return the...
摘要:找到開頭的某個進行切割。剩下的部分就是相同的子問題。記憶化搜索,可以減少重復部分的操作,直接得到后的結果。得到的結果和這個單詞組合在一起得到結果。 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome...
閱讀 4913·2023-04-25 18:47
閱讀 2673·2021-11-19 11:33
閱讀 3445·2021-11-11 16:54
閱讀 3101·2021-10-26 09:50
閱讀 2540·2021-10-14 09:43
閱讀 665·2021-09-03 10:47
閱讀 671·2019-08-30 15:54
閱讀 1498·2019-08-30 15:44