首页 > 代码库 > [LeetCode 471] Encode String with Shortest Length
[LeetCode 471] Encode String with Shortest Length
Trick: int r = (sub + sub).find(sub, 1); 寻找重复pattern。sub.size() % r == 0一定成立。否则设r是查找结果，总能找到更小的r满足条件。
1 class Solution { 2 public: 3 string encode(string s) { 4 int n = s.size(); 5 vector<vector<string>> dp(n + 1, vector<string>(n + 1)); 6 for (int i = 0; i < n; i++) { 7 dp[i][i + 1].push_back(s[i]); 8 } 9 for (int k = 2; k <= n; k++) {10 for (int i = 0, j = k; j <= n; i++, j++) {11 dp[i][j] = dp[i][j - 1] + dp[j - 1][j];12 for (int m = i + 1; m < j; m++) {13 string tmp = dp[i][m] + dp[m][j];14 if (tmp.size() < dp[i][j].size()) {15 dp[i][j] = tmp;16 }17 }18 int len = j - i;19 string sub = s.substr(i, len);20 int r = (sub + sub).find(sub, 1);21 if (r < len) {22 string tmp = to_string(len / r) + "[" + dp[i][i + r] + "]";23 if (tmp.size() < dp[i][j].size()) {24 dp[i][j] = tmp;25 }26 }27 }28 }29 return dp[0][n];30 }31 };
[LeetCode 471] Encode String with Shortest Length
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。