471. Encode String with Shortest Length

SillyMonkey 發(fā)布于2019-08-14 17:28 / 717人閱讀

摘要：題目鏈接這題還是有點(diǎn)難想的，一開始的思路想的還不對，參考這個(gè)博客的解釋表示最短的壓縮結(jié)果，里面枚舉切分點(diǎn)，分別得到和求和，找到長度最短的。這道題關(guān)鍵是找這種可壓縮的情況，其中。

471. Encode String with Shortest Length

題目鏈接：https://leetcode.com/problems...

這題還是有點(diǎn)難想的，一開始dp的思路想的還不對，參考這個(gè)博客的解釋：http://www.cnblogs.com/grandy...

dpi表示s[i, j]最短的壓縮結(jié)果，subproblem里面枚舉切分點(diǎn)k，分別得到dpi和dpk+1求和，找到長度最短的。

這道題關(guān)鍵是找sub = abcabc這種可壓縮的情況，其中sub = s[i,j]。方法比較巧妙，用sub+sub = abcabcabcabc，找第二個(gè)s在s+s里出現(xiàn)的位置，如果不是len(sub)，則說明sub有重復(fù)，那么就要壓縮這個(gè)sub，重復(fù)次數(shù)是len(sub) / indexOf(sub, 1)，重復(fù)的string用的是之前壓縮過的dpi，index = indexOf(sub, 1)。

public class Solution {
    public String encode(String s) {
        int n = s.length();
        String[][] dp = new String[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = "" + s.charAt(i);
        // j - i
        for(int len = 1; len < n; len++) {
            for(int i = 0; i + len < n; i++) {
                int j = i + len;
                // enumerate seperate k
                for(int k = i; k < j; k++) {
                    int left = dp[i][k].length();
                    int right = dp[k+1][j].length();
                    // update shortest encoded string within (i, j)
                    if(dp[i][j] == null || left + right < dp[i][j].length()) {
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                // update string within (i, j), encode abcabc
                String sub = s.substring(i, j + 1);
                int index = (sub + sub).indexOf(sub, 1);
                if(index < sub.length()) {
                    sub = (sub.length() / index) + "[" + dp[i][i+index-1] + "]";
                }
                if(dp[i][j] == null || dp[i][j].length() > sub.length()) {
                    dp[i][j] = sub;
                }
            }
        }
        
        return dp[0][n-1];
    }
}