首页 > 代码库 > [Leetcode] Palindrome Partitioning II
[Leetcode] Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Solution:
1 首先，利用createTable来标记所有是palindrome的片段。
2 初始化cut[]里的值
3 结合state表和cut表的初始值来update。
1 public class Solution { 2 public int minCut(String s) { 3 if(s==null||s.length()==0||s.length()==1) 4 return 0; 5 int N=s.length(); 6 boolean[][] state=createTable(s); 7 int[] cut=new int[N+1]; 8 cut[N-1]=0; 9 for(int i=N-1;i>=0;--i){10 cut[i]=N-i;11 for(int j=i;j<N;++j){12 if(state[i][j]){13 cut[i]=Math.min(cut[i], 1+cut[j+1]);14 }15 }16 }17 return cut[0]-1;18 }19 20 private boolean[][] createTable(String s) {21 // TODO Auto-generated method stub22 boolean[][] b=new boolean[s.length()][s.length()];23 for(int i=0;i<s.length();++i){24 b[i][i]=true;25 }26 int low=0;27 int high=0;28 for(int i=1;i<s.length();++i){29 //even30 low=i-1;31 high=i;32 while(low>=0&&high<s.length()&&s.charAt(low)==s.charAt(high)){33 b[low--][high++]=true;34 }35 //odd36 low=i-1;37 high=i+1;38 while(low>=0&&high<s.length()&&s.charAt(low)==s.charAt(high)){39 b[low--][high++]=true;40 }41 }42 return b;43 }44 }
[Leetcode] Palindrome Partitioning II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。