Alibi

My Life is Getting Better

Leetcode[131, 132] Palindrome Partitioning

10 Nov 2015

###Task1 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”] ]

###Python

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        ret = []
        self.findAll(s, ret, [])
        return ret
    def isPalin(self, s):
        if len(s) == 0:
            return False
        left = 0
        right = len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    def findAll(self, s, ret, temp):
        if len(s) == 0:
            ret.append(temp[:])
            return
        for i in range(len(s)):
            if self.isPalin(s[:i + 1]):
                temp.append(s[:i + 1])
                self.findAll(s[i + 1:], ret, temp)
                temp.pop()

###Java

public class Solution {
	public boolean isPalindrome(String s) {
		int i = 0;
		int j = s.length() - 1;
		while (i < j) {
			if (s.charAt(i) != s.charAt(j)) {
				return false;
			}
			i++;
			j--;
		}
		return true;
	}

	public void partitionHelper(List<List<String>> res, List<String> temp, String s, int pos) {
		if (pos == s.length()) {
			res.add(new ArrayList<String>(temp));
			return;
		}
		for (int i = pos + 1; i <= s.length(); i++) {
			if (isPalindrome(s.substring(pos, i))) {
				temp.add(s.substring(pos, i));
				partitionHelper(res, temp, s, i);
				temp.remove(temp.size() - 1);
			}
		}

		return;
	}

    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
        	return null;
        }

        List<List<String>> res = new ArrayList<List<String>>();
        List<String> temp = new ArrayList<String>();

        partitionHelper(res, temp, s, 0);

        return res;
    }
}

###Task2 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. ###Python

class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [i - 1 for i in range(len(s) + 1)]
        pan = self.isPalin(s)
        for i in range(2, len(s) + 1):
            for j in range(i):
                if pan[j][i - 1]:
                    dp[i] = min(dp[i], dp[j] + 1)
        return dp[len(s)]
    def isPalin(self, s):
        pan = [[False for i in range(len(s))] for j in range(len(s))]
        for i in range(len(s)):
            pan[i][i] = True
        for i in range(1, len(s)):
            if s[i] == s[i - 1]:
                pan[i - 1][i] = True
        for i in range(2, len(s)):
            j = 0
            while j + i < len(s):
                pan[j][j + i] = pan[j + 1][j + i - 1] and s[j] == s[j + i]
                j += 1
        return pan

###Java

public class Solution {
        public boolean[][] isPalindrome(String s) {
            boolean[][] res = new boolean[s.length()][s.length()];
            for (int i = 0; i < s.length(); i++) {
                res[i][i] = true;
            }
            for (int i = 0; i < s.length() - 1; i++) {
                if (s.charAt(i) == s.charAt(i + 1)) {
                    res[i][i + 1] = true;
                }
            }
            for (int length = 2; length < s.length(); length++) {
                for (int start = 0; start + length < s.length(); start++) {
                    res[start][start + length] = res[start + 1][start + length - 1] && (s.charAt(start) == s.charAt(start + length));
                }
            }

            return res;
        }
        
        public int minCut(String s) {
            //edge cases
            if (s == null || s.length() == 0) {
                return -1;
            }

            //let cuts[i] stands for the minimum number of cuts to get palindromes
            int[] cuts = new int[s.length() + 1];
            boolean[][] getPalindrome = isPalindrome(s);
            for (int i = 0; i <= s.length(); i++) {
                cuts[i] = i - 1;
            }
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 0; j < i; j++) {
                    if (getPalindrome[j][i - 1]) {
                        cuts[i] = Math.min(cuts[i], cuts[j] + 1);
                    }
                }
            }

            return cuts[s.length()];
        }
}

###Points

时间复杂度是O(n^2)。空间上需要一个二维数组来保存字典和一个线性数组来保存动态规划信息，所以是O(n^2) 如果求解所有结果时，他们没有多项式时间的解法，复杂度取决于结果数量，而当求解某一种统计的特殊量时，用动态规划就会很大的优势，可以降低时间复杂度。

Related Posts