[LeetCode] 647. Palindromic Substrings

 Problem: https://leetcode.com/problems/palindromic-substrings/

class Solution {
    public int countSubstrings(String s) {
        int N = s.length();
        
        boolean[][] dp = new boolean[N][N];
        int result = 0;
        
        for (int i= N-1; i >= 0; i--) {
            for (int j = N-1; j >= i; j--) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i+1][j-1]);
                if (dp[i][j]) {
                    result += 1;
                }
            }
        }
        
        return result;
    }
}

[LeetCode] 234. Palindrome Linked List

Problem : https://leetcode.com/problems/palindrome-linked-list/

Use post-order traversal to check the input string recursively.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        left = 0
        
        def postorder(node, right):
            nonlocal head
            nonlocal left
            
            if node:
                tmp = postorder(node.next, right + 1)
                if not tmp:
                    return tmp
                
                if left < right:
                    if node.val != head.val:
                        return False
                
                    head = head.next
                    left += 1
                
                return True
                
            return True
        
        return postorder(head, 0)

[LeetCode] 214. Shortest Palindrome

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

The quiz asks to add character only in front of the original string.

That means the characters be added in front must come from the end of the string and in reversed order. 

Generally it is the form of   [R'] + [Palindrome] + [R].

R' = reversed R

Let S' = revered S, then there must be S'[i:] == S[:Len(S) - i].  The answer is adding the longest S'[0:i] in front of S

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        r = s[::-1]
        
        for i in range(len(s)):
            if r[i:] == s[:len(s)-i]:
                return r[:i] + s
        
        return s

[LeetCode] 132. Palindrome Partitioning II

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

This problem includes 2 sub-problems.

Let isPalindrome[i][j] = True if s[i:j+1] is a palindrome string.

The transformation formula is

isPalindrome[i][j] = True,  when:

1)  s[i] == s[j]  and j - i <= 2     # i.e. "aa" or "aba"

2)  s[i] == s[j]  and isPalindrome[i+1][j-1] == True.   # i.e.  "a ****  a"

Let minCut[i] = min cut needed for s[0:i+1]

For any s[0:i+1], it can be split into 2 parts:  s[0:j] and s[j:i+1]

if s[j : j + 1] is a palindrome,  then minCut[i] = min( minCut[i], minCut[j-1] + 1 )

if s[0: j + 1] is already a palindrome, minCut[i] = 0

class Solution:
    def minCut(self, s: str) -> int:
        if not s:
            return 0
        
        # isPalindrome[i][j] = True if s[i:j+1] is palindrome string
        isPalindrome = [[False] * len(s) for _ in range(len(s))]
        
        for j in range(len(s)):
            for i in range(j+1):
                if s[i] == s[j] and (j - i <= 2 or isPalindrome[i+1][j-1] == True):
                    isPalindrome[i][j] = True
        
        
        # minCut[i] = min cut of s[0:i+1]
        minCut = [i for i in range(len(s))]
        
        for i in range(len(s)):
            for j in range(i+1):
                if isPalindrome[j][i]:
                    if j == 0:
                        # s[0:i+1] is already a palindrome
                        # no need to cut
                        minCut[i] = 0
                        break
                    
                    minCut[i] = min(minCut[i], minCut[j-1] + 1)
    
        return minCut[-1]

The top-down memorization + backtracking solution:

class Solution:
    def minCut(self, s: str) -> int:
        
        @cache
        def isPalindrome(left, right):
            if left >= right:
                return True
            
            if right - left == 1:
                return True
                
            if s[left] == s[right-1] and isPalindrome(left+1, right-1):
                return True
            
            return False
        
        @cache
        def helper(left, right):
            if isPalindrome(left, right):
                # s[left:right] is already a palindrome. no need to cut.
                return 0
            
            result = right - left - 1
            
            for mid in range(left+1, right):
                if isPalindrome(left, mid):
                    # s[left:mid] is palindrome, we can try to cut it at 'mid' and calculate the least cut of rest of string
                    result = min(result, 1 + helper(mid, right))
            
            return result
        
        return helper(0, len(s))

Edited on 08/07/2021. Add the top-down memorization + backtracking solution.

[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.

[LeetCode] 125. Valid Palindrome

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

Use two pointers to compare letters from head and tail. And ignore none-alpha-num letter.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
                
            while i < j and not s[j].isalnum():
                j -= 1
                
            if i < j and s[i].lower() != s[j].lower():
                break
            
            i += 1
            j -= 1
       
        return i >= j

[LeetCode] 9. Palindrome Number

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

Simulate the process to check if the first and last digit are the same.

Recursive solution:

Time Complexity : O (log(x))
Space Complexity: O (1)

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False

        def helper(x, radix):
            if radix == 0 or x == 0:
                return True

            firstDigit = x // (10 ** radix)
            lastDigit = x % 10

            if firstDigit != lastDigit:
                return False

            return helper((x - firstDigit * (10 ** radix) - lastDigit) // 10, radix - 2)

        radix = 0
        while 10 ** (radix + 1) <= x:
            radix += 1

        return helper(x, radix)

Iterative solution:

Time Complexity : O(log(x))
Space Complexity: O(1)

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """

        if x < 0:
            return False

        left = 0
        while 10 ** (left+1) <= x:
            left += 1

        right = 0

        leftx = x
        rightx = x
        while left >= right:
            l = leftx // (10 ** left)
            r = rightx % 10

            if l != r:
                return False

            rightx = rightx // 10
            right += 1

            leftx = leftx - l * (10 ** left)
            left -= 1

            if rightx != 0 and leftx == 0:
                return False

            if rightx == 0 and leftx != 0:
                return False

        return True

[LeetCode] 5. Longest Palindromic Substring

Problem: https://leetcode.com/problems/longest-palindromic-substring/

Since every individual character is a valid palindrome.  We may loop the string and expand the left and right boundary of each character to find the longest palindrome centered by this character.

Time Complexity :  O(len(s) * len(s))
Space Complexity :  O( len(s) ),  for space used by the tmp substrings

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """

        L = len(s)

        def palindrome(left, right):
            while left >= 0 and right < L:
                if s[left] != s[right]:
                    break

                left -= 1
                right += 1

            return s[left+1: right]

        result = ""

        i = 0
        while i < L:
            tmp = palindrome(i-1, i+1)
            if len(result) < len(tmp):
                result = tmp

            if i + 1 < L and s[i] == s[i+1]:
                tmp = palindrome(i-1, i+2)
                if len(result) < len(tmp):
                    result = tmp

            i += 1

        return result

This problem has optimal substructure.

Let dp[i+1][j-1] = True when substring s[i+1:j-1] is a palindrome.
Then substring s[i: j+1] is palindrome when s[i] == s[j] and dp[i+1][j-1] = True.
Or substring s[i: j+1] is palindrome when s[i] == s[j] and j - i == 1 which means s[i] is conjuct with s[j].

Greedy approach does not apply to this problem. Because if we only record the longest palindrome ends by s[i] which is s[j] ... s[i],  there could be a s[k] ( k > j ) can make a longer palindrome s[k] ... s[i]s[i+1]. But s[k] .. s[i] is a shorter palindrome than s[j] .. s[i].  ( i.e.  s = "aaaa" ).

Time Complexity = O(len(s) * len(s))
Space Complexity = O(1)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        N = len(s)
        
        # dp[left][right] = True if s[left:right+1] is palindrome
        dp = [[False] * N for _ in range(N)]
        
        resultStart = 0
        resultLen = 1
        
        for i in range(N):
            dp[i][i] = True
        
        # iterate backward because dp[left][right] depends on dp[left+1][right-1]
        for left in reversed(range(N)):
            for right in range(left+1, N):
                if s[left] == s[right]:
                    if right - left == 1 or dp[left+1][right-1]:
                        dp[left][right] = True
                
                        if right - left + 1 > resultLen:
                            resultLen = right - left + 1
                            resultStart = left
        
        return s[resultStart:resultStart + resultLen]

The equivalent Java solution:

class Solution {
    public String longestPalindrome(String s) {
        int N = s.length();
        boolean [][] dp = new boolean[N][N];
        
        int maxLen = 1;
        int left = N-1;
        
        for (int l = N-1; l >= 0; l--) {
            for (int r = N-1; r >= l; r--) {
                // s[l:r] is a palindrome is s[l] == s[r] and s[l+1:r-1] is a palindrome
                dp[l][r] = s.charAt(l) == s.charAt(r) && (r - l <= 1 || dp[l+1][r-1]);
                if (dp[l][r] && r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    left = l;
                }
            }
        }
        
        return s.substring(left, left + maxLen);
    }
}

Use hash table to trim unnecessary comparings.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        @lru_cache(maxsize = None)
        def isPalindrom(left, right):
            return left >= right or s[left] == s[right] and isPalindrom(left+1, right-1)
        
        
        N = len(s)
        if N <= 1: return s
        
        result = ""
        seen = defaultdict(list)
        
        for left in reversed(range(N)):
            seen[s[left]].append(left)
            
            for right in seen[s[left]]:
                if isPalindrom(left, right) and right - left + 1 > len(result):
                    result = s[left:right+1]
                    break
     
        return result

Use BFS approach to expand from center.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        queue = deque()
        
        N = len(s)
        if N <= 1: return s
        
        result = (0, 0)
        resultLen = 1
        
        for i in range(N):
            queue.append((i,i))
            
            if i + 1 < N and s[i] == s[i+1]:
                queue.append((i, i+1))
        
        while queue:
            left, right = queue.popleft()
            if right - left + 1 > resultLen:
                result = (left, right)
                resultLen = right - left + 1

            if left - 1 >= 0 and right + 1 < N and s[left-1] == s[right+1]:
                queue.append((left-1, right+1))
        
        left, right = result
        return s[left: right+1]

Edited on 11/21/2021. Add the Java solution.