Palindrome Partitioning II

原题: https://leetcode.com/problems/palindrome-partitioning-ii/description/

题意: 给定一个字符串s,对其进行划分,要求划分后的所有字符串都是回文串,求最小划分的个数。

例子: 

给定 s="aab"
返回 1(对应的回文串为:["aa","b"])

标签: palindrome、partitioning、回文、ii、划分、面试
猜你感兴趣的圈子:
LeetCode交流圈
  • Bingo
    2017-08-13 12:21:33 1楼#1层
    Java:
    public class Solution {  
        public int minCut(String s) {  
            if(s==null||s.length()==0||s.length()==1) {  
                return 0;  
            }  
            int[][] palindrome_map = new int[s.length()][s.length()];  
            int[] cut_num_array = new int[s.length() + 1];  
              
            for(int i=s.length()-1;i>=0;i--) {  
                cut_num_array[i] = s.length() - i;  
                for(int j=i;j<s.length();j++) {  
                    if(s.charAt(i)==s.charAt(j)) {  
                        if(j-i<2||palindrome_map[i+1][j-1]==1) {  
                            palindrome_map[i][j]=1;  
                            cut_num_array[i] = Math.min(cut_num_array[i], cut_num_array[j+1]+1);  
                        }  
                    }  
                }  
                  
            }  
          
            return cut_num_array[0] - 1;  
        }  
    }
  • Bingo
    2017-08-13 12:21:59 2楼#1层
    C++:
    class Solution {
    public:
        int minCut(string s) {
            int len = s.size();
            bool P[len][len];
            int dp[len + 1];
            for (int i = 0; i <= len; ++i) {
                dp[i] = len - i - 1;
            }
            for (int i = 0; i < len; ++i) {
                for (int j = 0; j < len; ++j) {
                    P[i][j] = false;
                }
            }
            for (int i = len - 1; i >= 0; --i) {
                for (int j = i; j < len; ++j) {
                    if (s[i] == s[j] && (j - i <= 1 || P[i + 1][j - 1])) {
                        P[i][j] = true;
                        dp[i] = min(dp[i], dp[j + 1] + 1);
                    }
                }
            }
            return dp[0];
        }
    };
  • 回复
隐藏