首页 > 代码库 > [leetcode]Palindrome Partitioning
[leetcode]Palindrome Partitioning
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"] ]
算法思路：
dfs
1 public class Solution { 2 List<List<String>> result = new ArrayList<List<String>>(); 3 4 public List<List<String>> partition(String s) { 5 if(s == null || s.length() == 0) return result; 6 dfs(new ArrayList<String>(),s); 7 return result; 8 } 9 private void dfs(List<String> list,String s){10 if(s.length() == 0){11 result.add(new ArrayList<String>(list));12 return;13 }14 for(int i = 0; i < s.length(); i++){15 String pre = s.substring(0, i + 1);16 if(isPalindrome(pre)){17 list.add(pre);18 dfs(list, s.substring(i + 1));19 list.remove(list.size() - 1);20 }21 }22 }23 private boolean isPalindrome(String s){24 for(int i = 0; i <= s.length() / 2; i++){25 if(s.charAt(i) != s.charAt(s.length() - 1 - i)) return false;26 }27 return true;28 }29 }
jd的做法几乎一样，并在博文下面借鉴了两篇其他博文，其中有个DP算法可以看一下。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。