Python solution with detailed explanation


  • 0
    G

    Solution

    Encode String with Shortest Length https://leetcode.com/problems/encode-string-with-shortest-length/

    Memoization: Time: O(N^3)

    • String based problem can be broken down into smaller sized problem involving sub-strings of the larger string.
    • For memoization, we generally parameterize a subtring as s(i,j). For DP, we can parameterize it in terms of substrings of length 1, 2, 3, ..., L.
    • Given a substring s(i,j), we have three choices for finding minimum encoding:
    • X = Do not encode s(i,j)
    • Y = Find all repeating patterns and encodings and then choose the minimum length encoding. Length of repeating pattern ranges from N//2 to 1.
    • Z = Split s(i,j) into two substrings left and right. s(i,k) and s(k+1,j). If left and right are same, then we have another candidate "2[left]". Now k ranges from i to j-1. Finally choose the minimun length encoding from all these possibilities.
    • s(i,j) = min(X, Y, Z, key=len)
    • Note: we use min method in Python to find the shortest string based on length.
    • Time Complexity: O(N^3) - There are N^2 sub-problems and every sub-problem can be solved in O(N).
    • Space Complexity: O(N^2)
    class Solution(object):
        def find_repeating_pattern(self, s):
            N = len(s)
            min_so_far = s
            for i in range(N//2, 0, -1):
                if N%i == 0:
                    if self.test(i, s):
                        cnt, pattern = N//i, s[0:i]
                        min_so_far = min("%d[%s]" %(cnt, pattern), min_so_far, key=len) if cnt > 0 else min_so_far
            return min_so_far        
    
        def test(self, i, s):
            pattern = s[0:i]
            for j in range(i, len(s)-i + 1,i):
                match = s[j:j+i]
                if pattern != match:
                    return False
            return True
        
        def helper(self, s, i, j, cache):
            if j < i:
                return ""
            elif i == j:
                return s[i]
            elif i in cache and j in cache[i]:
                return cache[i][j]
            else:
                cache.setdefault(i, {})[j] = self.find_repeating_pattern(s[i:j+1])
                for k in range(i, j):
                    left, right = self.helper(s, i, k, cache), self.helper(s, k+1, j, cache)
                    if left == right:
                        cache[i][j] = min(cache[i][j], left + right, "2[%s]" %(left), key=len)
                    else:
                        cache[i][j] = min(cache[i][j], left+right, key=len)
                return cache[i][j]
        
        def encode(self, s):
            """
            :type s: str
            :rtype: str
            """
            cache = {}
            return self.helper(s, 0, len(s)-1, cache)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.