首页 > 代码库 > LeetCode 131 Palindrome Partitioning
LeetCode 131 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.判断字符串的字串S.subString(i,j) [i<=j]是否为为回文子串,用boolean型的二维数组isPalindrome来存储该结果。在这个地方用了点小技巧,isPalindrome[i]j]会依赖于isPalindrome[i+1]j-1] [i+2<=j].
2.假设在求String s的所有回文子串,我们已经知道了s.substring(0,0),s.substring(0,1),s.substring(0,2),s.substring(0,3),....,s.substring(0,s.length()-2)的所有回文字串,那我们只需要遍历isPalindrome[i]js.lenth()-1]是不是true{即从s.substring(i)是不是回文字符串}若为true,我们取出s.substring(i-1)的所有回文字串,并在每一种可能性末尾添加s.substring(i)即可,代码如下
public class Solution { public boolean[][] isPalindrome(String s) { boolean[][] isPalindrome = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) isPalindrome[i][i] = true; for (int i = 0; i < s.length() - 1; i++) isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1)); for (int length = 2; length < s.length(); length++) { for (int start = 0; start + length < s.length(); start++) { isPalindrome[start][start + length] = isPalindrome[start + 1][start + length - 1] && s.charAt(start) == s.charAt(start + length); } } return isPalindrome; } public List<List<String>> partition(String s) { boolean[][] isPalindrome= isPalindrome(s); HashMap<Integer,List<List<String>>> hm=new HashMap<Integer,List<List<String>>>(); for(int i=0;i<s.length();i++){ List<List<String>> ls=new ArrayList<List<String>>(); if(isPalindrome[0][i]){ ArrayList<String> temp=new ArrayList<String>(); temp.add(s.substring(0, i+1)); ls.add(temp); } for(int j=1;j<=i;j++){ if(isPalindrome[j][i]){ List<List<String>> l=hm.get(j-1); List<List<String>> al=new ArrayList<List<String>>(); for(List<String> temp:l){ ArrayList<String> clone=new ArrayList<String>(temp); clone.add(s.substring(j, i+1)); al.add(clone); } ls.addAll(al); } } hm.put(i,ls); } return hm.get(s.length()-1); } }
LeetCode 131 Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。