# Python solution with detailed explanation

• 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)
``````

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