Note:
1. We start with different position and different length to find the shortening.
2. It satisfy following conditions :
I. if length < 4, it short does not help. number [char] takes four pos.
II. Since shortening happen, we can see whether a substring can be combined by two shortened words. k from [i, j]. dp[i][k] and dp[k + 1][j].
III Find all the possible shortening: i) length module should be 0. ii)) After all the replacement length should be 0.
class Solution { ???public String encode(String s) { ???????String[][] dp = new String[s.length()][s.length()]; ???????????????for (int l = 0; l < s.length(); l++) { ???????????for (int i = 0; i < s.length() - l; i++) { ???????????????int j = i + l; ???????????????String subStr = s.substring(i, j + 1); ???????????????dp[i][j] = subStr; ???????????????if (j - i < 4) { ???????????????????continue; ???????????????} ???????????????for (int k = i; k < j; k++) { ???????????????????if ((dp[i][k].length() + dp[k + 1][j].length()) < dp[i][j].length()) { ???????????????????????dp[i][j] = dp[i][k] + dp[k + 1][j]; ???????????????????} ???????????????} ???????????????????????????????for (int k = 0; k < subStr.length(); k++) { ???????????????????String repeat = subStr.substring(0, k + 1); ???????????????????if (repeat != null && subStr.length() % repeat.length() == 0 && subStr.replaceAll(repeat, "").length() == 0) { ???????????????????????String result = subStr.length() / repeat.length() + "[" + dp[i][i + k] + "]"; ???????????????????????if (result.length() < dp[i][j].length()) { ???????????????????????????dp[i][j] = result; ???????????????????????} ???????????????????} ???????????????} ???????????} ???????} ???????return dp[0][s.length() - 1]; ???}}LeetCode 471: Encode String with Shortest Length
原文地址：http://www.cnblogs.com/shuashuashua/p/7672517.html