471. Encode String with Shortest Length
一道对角线型dp题目，对角线是我自己总结的说法，就是要先初始化对角线上的区间，然后再一层一层朝外扩展。这样的题目第一层用距离来表示，然后循环i，然后计算出j，这样我觉得比较好想一些
class Solution(object):
def encode(self, s):
"""
:type s: str
:rtype: str
"""
# 又是有点像对角线DP
# dp[i][j]表示i,j之间的string可以encode成某个string
dp = [["" for _ in range(len(s))] for _ in range(len(s))]
for l in range(len(s)):
for i in range(len(s)-l):
j = i+l
substr = s[i:j+1]
# Checking if string length < 5. In that case, we know that encoding will not help.
if j - i < 4:
dp[i][j] = substr
else:
dp[i][j] = substr
for k in range(i, j):
if len(dp[i][k] + dp[k+1][j]) < len(dp[i][j]):
dp[i][j] = dp[i][k] + dp[k+1][j]
# Loop for checking if string can itself found some pattern in it which could be repeated.
for k in range(len(substr)):
repeatStr = substr[0:k+1]
d = len(substr)/len(repeatStr)
if repeatStr and len(substr)%len(repeatStr) == 0 and substr == repeatStr*d:
ss = str(d) + "[" + dp[i][i+k] + "]"
if len(ss) < len(dp[i][j]):
dp[i][j] = ss
return dp[0][len(s)-1]
