首页 > 代码库 > Leetcode: Palindrome Partitioning
Leetcode: 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"] ]
难度:98,与Word Break II问题一样,NP(枚举)与DP结合的问题。参考了网上的做法,这道题是求一个字符串中回文子串的切割,并且输出切割结果,其实是Word Break II和Longest Palindromic Substring结合,该做的我们都做过了。首先我们根据Longest Palindromic Substring中的方法建立一个字典,得到字符串中的任意子串是不是回文串的字典。接下来就跟Word Break II一样,根据字典的结果进行切割,然后按照循环处理递归子问题的方法,如果当前的子串满足回文条件,就递归处理字符串剩下的子串。如果到达终点就返回当前结果。算法的复杂度跟Word Break II一样,取决于结果的数量,最坏情况是指数量级的。
这里建立字典以方便查找String s中任意substring是不是回文,用到了DP,用法很精髓。
1 public class Solution { 2 public ArrayList<ArrayList<String>> partition(String s) { 3 ArrayList<ArrayList<String>> partitions = new ArrayList<ArrayList<String>>(); 4 if (s == null || s.length() == 0) { 5 return partitions; 6 } 7 boolean[][] dic = getdict(s); 8 ArrayList<String> partition = new ArrayList<String>(); 9 helper(s, dic, 0, partition, partitions);10 return partitions;11 }12 13 public void helper(String s, boolean[][] dic, int starter, ArrayList<String> partition, ArrayList<ArrayList<String>> partitions) {14 if (starter == s.length()) {15 partitions.add(new ArrayList<String>(partition));16 return;17 }18 for (int j=starter; j<s.length(); j++) {19 if (dic[starter][j]) {20 partition.add(s.substring(starter, j+1));21 helper(s, dic, j+1, partition, partitions);22 partition.remove(partition.size() - 1);23 }24 }25 }26 27 public boolean[][] getdict(String s) {28 boolean[][] dic = new boolean[s.length()][s.length()];29 for (int i=s.length()-1; i>=0; i--) {30 for (int j=i; j<s.length(); j++) {31 if ((s.charAt(i) == s.charAt(j)) && ((j-i<2) || dic[i+1][j-1])) {32 dic[i][j] = true;33 }34 }35 }36 return dic;37 }38 }
Leetcode: Palindrome Partitioning
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。