**Palindrome Partitioning

本文主要是介绍**Palindrome Partitioning，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

https://leetcode.com/problems/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"]]

分析：

http://blog.csdn.net/linhuanmars/article/details/22777711

这里getDcit方法与上一篇中的dp数组的求解方法完全一样啊！！！

public class Solution {
public List<List<String>> partition(String s) {List<List<String>> res = new ArrayList<List<String>>();if(s==null || s.length()==0)return res;helper(s, getDict(s),0,new ArrayList<String>(), res);return res;
}
private void helper(String s, boolean[][] dict, int start, ArrayList<String> item, List<List<String>> res)
{if(start==s.length()){res.add(new ArrayList<String>(item));return;}for(int i=start;i<s.length();i++){if(dict[start][i]){item.add(s.substring(start,i+1));helper(s,dict,i+1,item,res);item.remove(item.size()-1);}}
}
private boolean[][] getDict(String s)
{boolean[][] dict = new boolean[s.length()][s.length()];for(int i=s.length()-1;i>=0;i--){for(int j=i;j<s.length();j++){if(s.charAt(i)==s.charAt(j) && ((j-i<2)||dict[i+1][j-1])){dict[i][j] = true;}}}return dict;
}
}

这篇关于**Palindrome Partitioning的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---