LC 93 & LC 131

Solution to LeetCode 93 Restore IP Addresses & LeetCode 131 Palindrome Partitioning

LeetCode 131

Palindrome Partitioning (Medium) [link]

The recursion tree branches for different partitions. The stop criteria is 1) when the new partition is not a palindrome 2) when we completed all partitions.

There are ways to determine a palindrome: 1) use two pointers starting from the first and the last character to check whether each pair is the same 2) If the string is equal to the reversed string, then it’s a palindrome.

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        path = []
        
        def backtrack(s, start):
            if start >= len(s):
                res.append(path[:])
                return
            
            for i in range(start, len(s)):
                temp = s[start:i+1]
                if temp == temp[::-1]:
                    path.append(temp)
                    backtrack(s, i+1)
                    path.pop()
                else:
                    continue
            
        backtrack(s, 0)
        return res

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []
        path = []
        def backtrack(s, start):
            if start >= len(s):
                res.append(path[:])
                return
            
            for i in range(start, len(s)):
                
                if self.isPalindrome(s, start, i):
                    path.append(s[start:i+1])
                    backtrack(s, i+1)
                    path.pop()
                else:
                    continue
    
        backtrack(s, 0)
        return res

    def isPalindrome(self, s, start, end):
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        
        return True

LeetCode 93

Restore IP Addresses (Medium) [link]

There should be four parts of the string, so the depth of the recursion tree should be four. The maximum number is 255, so the there are at most three for loops. The stoping criteria is that 1) any partition results in a number that is not between 0 and 255, 2) we got four partitions.

Remember to add separator ‘.’. The next start index should start from i+2 because of the additional ‘.’. In the backtracking, remember to remove the separator ‘.’.

To determine whether a partition is not valid: 1) any number of length >1 and has a leading zero, 2) has any character that’s not a positive digit, 3) number larger than 255.

Rather than using path to record the string, we do the partition on the original string.

The time complexity is O(3^4 * n) where 3 is the maximum number of for loops, 4 is the maximum depth of the recursion tree, and n is the length of the string. It takes O(n) to save the string to the result list.

The space complexity is O(4) plus the space of the result list. The space complexity of the recursion is proportional to the depth of the recursion tree.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        if len(s) > 12: 
            return res

        def backtrack(s, start, point_num):
            if point_num == 3:
                if self.isvalid(s, start, len(s)-1):
                    res.append(s[:])
                return

            for i in range(start, len(s)):
                if self.isvalid(s, start, i):
                    s = s[:i+1]+"."+s[i+1:]
                    backtrack(s, i+2, point_num+1)
                    s = s[:i+1]+s[i+2:]
                else:
                    return

        backtrack(s, 0, 0)
        return res
    
    def isvalid(self, s, start, end):
        if start > end:
            return False
        if s[start] == "0" and start != end:
            return False
        if not 0 <= int(s[start:end+1]) <= 255:
            return False
        return True