8.22 - hard - 90

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]