[LeetCode] 131. Palindrome Partitioning

Problem : https://leetcode.com/problems/palindrome-partitioning/

Memorization Solution:

Step 1, find the first palindrome and put it to current partial result.

Step 2, repeat step1 to find palindrome in the rest string and append to partial result.

Stop repeating step 1 when rest string is empty.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result = []
        
        @lru_cache(maxsize = None)
        def isPalindrome(start, end):
            while start < end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            
            return True
        
        def helper(start, partial):
            if start == len(s):
                result.append(partial)
                return
            
            for i in range(start, len(s)):
                if isPalindrome(start, i):
                    helper(i+1, partial + [s[start:i+1]])
                   
        helper(0, [])
        
        return result

DP + DFS solution:

class Solution {
    int N;
    boolean[][] palindrome;
    Map<Integer, List<List<String>>> memo = new HashMap<>();
    
    public List<List<String>> partition(String s) {
        N = s.length();
        palindrome = new boolean[N][N];
        
        for (int left = N-1; left >= 0; left--) {
            for (int right = N-1; right >= left; right--) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right) && (right - left <= 1 || palindrome[left+1][right-1]);
            }
        }
        
        return helper(s, 0);
    }
    
    List<List<String>> helper(String s, int start) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        
        List<List<String>> result = new ArrayList<>();
        
        if (start >= N) {
            List<String> tmp = new ArrayList<>();
            result.add(tmp);
           
            return result;
        }
        
        for (int i = start; i < N; i++) {
            if (palindrome[start][i]) {
                for (List<String> suffix : helper(s, i+1)) {
                    List<String> tmp = new ArrayList<>();
                    tmp.add(s.substring(start, i+1));
                    tmp.addAll(suffix);
                    result.add(tmp);
                }
            }
        }
        
        memo.put(start, result);
        
        return result;
    }
}

DP solution:

Time complexity = O( N ** 2 )

class Solution {
    public List<List<String>> partition(String s) {
        int N = s.length();
        boolean[][] palindrome = new boolean[N][N];
        
        // memo[i] = palindrome partitions of s[i:]
        List<List<List<String>>> memo = new ArrayList<>(N+1);
        
        for (int i = 0; i < N; i++) {
            memo.add(new ArrayList<List<String>>());
        }
        
        // Add an empty partition list for position 'N'
        // memo[N] = [[]]
        memo.add(Arrays.asList(Collections.emptyList()));
        
        for (int left = N-1; left >= 0; left--) {
            for (int right = N-1; right >= left; right--) {
                palindrome[left][right] = s.charAt(left) == s.charAt(right) && (right - left <= 1 || palindrome[left+1][right-1]);
                
                if (palindrome[left][right]) {
                    // s[left:right+1] is a palindrome
                    // use it to expand the palindrome partitions of s[right+1:]
                    for (List<String> suffix : memo.get(right+1)) {
                        List<String> tmp = new ArrayList<>();
                        tmp.add(s.substring(left, right+1));
                        tmp.addAll(suffix);
                        memo.get(left).add(tmp);
                    }
                }
            }
        }
        
        // return palindrome partitions of s[0:]
        return memo.get(0);
    }
}

Edited on 04/13/2021. Add DP solution.

Edited on 01/04/2022. Refactor the DP + DFS solution.

Edited on 01/04/2022. Refactor the DP solution.