`
huntfor
  • 浏览: 201127 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Palindrome Partitioning II

 
阅读更多

新博文地址:

 

[leetcode]Palindrome Partitioning II

 

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.

 将字符串切成片,要求是每一段都是回文串。拿到这道题的第一反应就是用DP,但是状态转移方程实在是想不出来。。。。所以看了一下别人的算法,是厉害。

具体算法:

1.  确定字符串s的最小切割数

2. 则字符串 ‘#’ + s 的最小切割数则是遍历s,如果遇到‘#’(假设#在s中的索引是i)则'#' + s的切割数即为s.substring(1) 的切割数或者+ 1(如果#出现在s的最后一个位置,则不需要+1)

因此状态转移方程为 result[i] = min(result[i] , result[j + 1] + 1) (当j + 1 != length时)result[i] = min(result[i] , result[j + 1] )(当j + 1 == length时)

这个算法很腻害的是,没有计算某个字符子串是否是回文的,而是用一个二维数组来标记是否是回文,很值得借鉴。

不罗嗦了,代码如下:不明白可以吐槽

 

  public int minCut(String s) {
    	if( s == null || s.length() < 2){
    		return 0;
    	}
    	int[] result = new int[s.length() + 1];
    	boolean[][] map = new boolean[s.length()][s.length()];
    	for(int i = s.length() - 1; i >=0 ; i--){
    		result[i] = s.length() - i - 1;
    		for(int j = i ; j < s.length(); j++){
    			if(s.charAt(i) == s.charAt(j)){
    				if(j - i <= 1 || map[i + 1][j - 1] == true){
    					map[i][j] = true;
    					if(j == s.length() - 1){
    						result[i] = Math.min(result[i], result[j + 1]);
    					}
						result[i] = Math.min(result[i], result[j + 1] + 1);
    				}
    			}
    		}
    	}
    	return result[0];
    }

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics