首页 > 代码库 > Palindrome Partitioning

Palindrome Partitioning

2024-08-05 08:44:25   224人阅读

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"]

}
对于这道题，需要用到动态规划，首先用一张表记录下来回文数字的标识，但是有一点，在for循环中，外层从最后一个开始排，并依此递减，直到为0为止，内层循环则从外层i开始，依此递增。并依赖子问题来判断是否是回文。
 1 for(int i=len-1;i>=0;i--){ 2         for(int j=i;j<len;j++){ 3             if(i==j) 4             { 5                 table[i][j]=1; 6             }else{ 7                 if(s.charAt(i)==s.charAt(j)){ 8                     if(j==i+1||table[i+1][j-1]==1){ 9                         table[i][j]=1;10                     }11                 }12             }13         }14     }

之后依靠这张表来进行深度优先搜索遍历，对于二维表所表示的深度优先搜索可以采用这样的方法，

 1 public void DFS(String s,int begin,int [][]table,List<String> list,  List<List<String>> result){ 2     int len=table.length; 3     if(begin==len){ 4         result.add(list); 5         return;  6     } 7     for(int i=begin;i<len;i++){ 8         if(table[begin][i]==1){ 9             List<String> temp=new ArrayList<String>(list);10             temp.add(s.substring(begin, i+1));11             DFS(s,i+1,table,temp,result);12         }13     }14 }

对于每一次深度搜索的最终结果都加入一个list中，之后将这些list再放入整个result 的list中

 1 package Palindrome.Partitioning; 2  3 import java.util.ArrayList; 4 import java.util.List; 5  6 public class PalindromePartitioning { 7 public List<List<String>> partition(String s) { 8     int len=s.length(); 9     int [][] table=new int[len][len];10     List<List<String>> result=new ArrayList<List<String>>();11     List<String> list=new ArrayList<String>();12     if(s.length()==0||s==null){13         result.add(list);14     }15     //initialize16     for(int i=0;i<len;i++){17         for(int j=0;j<len;j++){18             table[i][j]=0;19         }20     }21     //get Palindrome table22     for(int i=len-1;i>=0;i--){23         for(int j=i;j<len;j++){24             if(i==j)25             {26                 table[i][j]=1;27             }else{28                 if(s.charAt(i)==s.charAt(j)){29                     if(j==i+1||table[i+1][j-1]==1){30                         table[i][j]=1;31                     }32                 }33             }34         }35     }36     DFS(s,0,table,list,result);37     return result;    38 }39 public void DFS(String s,int begin,int [][]table,List<String> list,  List<List<String>> result){40     int len=table.length;41     if(begin==len){42         result.add(list);43         return; 44     }45     for(int i=begin;i<len;i++){46         if(table[begin][i]==1){47             List<String> temp=new ArrayList<String>(list);48             temp.add(s.substring(begin, i+1));49             DFS(s,i+1,table,temp,result);50         }51     }52 }53 }

 

Palindrome Partitioning


联系
我们