首页 > 代码库 > [Leetcode][JAVA] Palindrome Partitioning
[Leetcode][JAVA] 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"] ]
回溯算法，需要注意的就是在得到子串时判断是否为回文字符串（需要自己写函数），如果是才继续展开下一层。
代码：
1 public List<List<String>> partition(String s) { 2 List<List<String>> re = new ArrayList<List<String>>(); 3 if(s==null || s.length()==0) 4 return re; 5 List<String> path = new ArrayList<String>(); 6 collect(re, path, s, 0); 7 return re; 8 } 9 public void collect(List<List<String>> re, List<String> path, String s, int start)10 {11 for(int i=start+1;i<=s.length();i++)12 {13 String temp = s.substring(start,i);14 if(!isP(temp))15 continue;16 path.add(temp);17 if(i==s.length())18 re.add(new ArrayList<String>(path));19 else20 collect(re, path, s, i);21 path.remove(path.size()-1);22 }23 }24 public boolean isP(String x)25 {26 int p = 0;27 int q = x.length()-1;28 while(p<q)29 {30 if(x.charAt(p)!=x.charAt(q))31 return false;32 p++;33 q--;34 }35 return true;36 }
[Leetcode][JAVA] Palindrome Partitioning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。