首页 > 代码库 > Palindrome Partitioning leetcode java
Palindrome Partitioning leetcode java
题目:
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"] ]
题解:
这道题还是一种找组合的可能性,类似于wordbreakii。
这里想法是,用递归循环找子问题的方法,把母串按所有组合可能性拆分,如果是回文,就加进来,当层数为s的length时就有一个结果了。
这里需要判断是否为回文。
利用validPalindrome的思想很容易就写出来了(这里不需要判断大小写还有有没有别的字符)。
代码如下:
1 public ArrayList<ArrayList<String>> partition(String s) {
2 ArrayList<String> item = new ArrayList<String>();
3 ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
4
5 if(s==null||s.length()==0)
6 return res;
7
8 dfs(s,0,item,res);
9 return res;
10 }
11
12 public void dfs(String s, int start, ArrayList<String> item, ArrayList<ArrayList<String>> res){
13 if (start == s.length()){
14 res.add(new ArrayList<String>(item));
15 return;
16 }
17
18 for (int i = start; i < s.length(); i++) {
19 String str = s.substring(start, i+1);
20 if (isPalindrome(str)) {
21 item.add(str);
22 dfs(s, i+1, item, res);
23 item.remove(item.size() - 1);
24 }
25 }
26 }
27
28
29 public boolean isPalindrome(String s){
30 int low = 0;
31 int high = s.length()-1;
32 while(low < high){
33 if(s.charAt(low) != s.charAt(high))
34 return false;
35 low++;
36 high--;
37 }
38 return true;
39 }
2 ArrayList<String> item = new ArrayList<String>();
3 ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
4
5 if(s==null||s.length()==0)
6 return res;
7
8 dfs(s,0,item,res);
9 return res;
10 }
11
12 public void dfs(String s, int start, ArrayList<String> item, ArrayList<ArrayList<String>> res){
13 if (start == s.length()){
14 res.add(new ArrayList<String>(item));
15 return;
16 }
17
18 for (int i = start; i < s.length(); i++) {
19 String str = s.substring(start, i+1);
20 if (isPalindrome(str)) {
21 item.add(str);
22 dfs(s, i+1, item, res);
23 item.remove(item.size() - 1);
24 }
25 }
26 }
27
28
29 public boolean isPalindrome(String s){
30 int low = 0;
31 int high = s.length()-1;
32 while(low < high){
33 if(s.charAt(low) != s.charAt(high))
34 return false;
35 low++;
36 high--;
37 }
38 return true;
39 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。