首页 > 代码库 > 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"] ]原题链接:https://oj.leetcode.com/problems/palindrome-partitioning/
题目;给定一个字符串s , 把s 分成每个子串都是回文串。
返回s 的所有可能的回文切分。
思路:根据对示例的结果的观察,发现需要两个list,一个用于放入所有的单个字符,一个用于放入第二次的切分结果。于是有了下面的程序,即现遍历一遍,将单个字符加入到list中去;再切分字符,判断是否是回文,如是,则加入到第二个list中去;最后返回结果。但是如下的方法总是在第二次的时候会漏掉单个字符。
public static List<List<String>> partition(String s) { List<List<String>> list = new ArrayList<List<String>>(); List<String> li = new ArrayList<String>(); int len = s.length(); if(len == 0) return list; for(int i=0;i<len;i++){ li.add(s.charAt(i)+""); } list.add(li); if(len == 1) return list; List<String> li1 = new ArrayList<String>(); boolean flag = false; for(int i=0;i<len;i++){ for(int j=i+1;j<len;j++){ String sub = s.substring(i, j+1); if(isPalindrome(sub)){ flag = true; li1.add(sub); } } } if(flag) list.add(li1); return list; } public static boolean isPalindrome(String s){ int len = s.length(); if(len <= 1) return true; for(int i=0;i<len;i++){ if(s.charAt(i) != s.charAt(len - i - 1)) return false; } return true; }
按照如上的程序,会与正确结果插肩而过。不过正确结果重复了呀。
Input: | "cdd" |
Output: | [["c","d","d"],["dd"]] |
Expected: | [["c","d","d"],["c","dd"]] |
这个题目考虑用动态规划解题,关键在于构造一个解空间,确定S的任意子串S(i, j)是不是对称的。判断标准如下:
1、如果i == j,则S(i, j)是对称的;
2、如果j - i == 1 && S[i] == S[j],则S(i, j)是对称的;
3、如果j - i > 1 && S[i] == S[j] && S(i + 1, j - 1)是对称的,则S(i, j)也是对称的。
在构造完这样的解空间后,就可以在O(1)时间内判定任意子串是不是对称的了。算法实现如下:
public ArrayList<ArrayList<String>> partition(String s) { ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>(); ArrayList<String> r = new ArrayList<String>(); int length = s.length(); boolean[][] map = new boolean[length][length]; findPartition(s, 0, ret, r, map); return ret; } private void findPartition(String s, int start, ArrayList<ArrayList<String>> ret, ArrayList<String> r, boolean[][] map) { int length = s.length(); if (start == length && r.size() != 0) { ArrayList<String> clone = new ArrayList<String>(r); ret.add(clone); } else { for (int j = start; j < length; j++) { if (start == j || (j - start > 1 && s.charAt(start) == s.charAt(j) && map[start + 1][j - 1]) || (j - start == 1 && s.charAt(start) == s.charAt(j))) { map[start][j] = true; r.add(s.substring(start, j + 1)); findPartition(s, j + 1, ret, r, map); r.remove(r.size() - 1); } } } }
[1] reference: http://www.blogjava.net/menglee/archive/2013/12/19/407778.html
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。