首页 > 代码库 > 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"] ]
答案
public class Solution { ArrayList<List<List<String>>> lists; String s; public boolean isPalindrome(int start, int end) { while (end > start) { if (s.charAt(end) != s.charAt(start)) { return false; } end--; start++; } return true; } public void calPartition(int index) { List<List<String>> result=lists.get(index); for (int end = index; end < s.length(); end++ ) { if(isPalindrome(index,end)) { String pString=s.substring(index,end+1); if(end==s.length()-1) { List<String>p=new LinkedList<String>(); p.add(pString); result.add(p); continue; } List<List<String>> p=lists.get(end+1); for(List<String>tmp:p) { List<String> t=new LinkedList<String>(); t.addAll(tmp); t.add(0, pString); result.add(t); } } } } public List<List<String>> partition(String s) { lists= new ArrayList<List<List<String>>>(s.length()); this.s = s; for (int i = 0; i < s.length(); i++ ) { lists.add(new LinkedList<List<String>>()); } for (int i = s.length()-1; i >=0; i-- ) { calPartition(i); } return lists.get(0); } }
Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。