Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/471.html
471. Encode String with Shortest Length (Hard)
Given a non-empty string, encode the string such that its encoded length is the shortest.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
Note:
- k will be a positive integer and encoded string will not be empty or have extra space.
- You may assume that the input string contains only lowercase English letters. The string's length is at most 160.
- If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them is fine.
Example 1:
Input: "aaa" Output: "aaa" Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.
Example 2:
Input: "aaaaa" Output: "5[a]" Explanation: "5[a]" is shorter than "aaaaa" by 1 character.
Example 3:
Input: "aaaaaaaaaa" Output: "10[a]" Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".
Example 4:
Input: "aabcaabcd" Output: "2[aabc]d" Explanation: "aabc" occurs twice, so one answer can be "2[aabc]d".
Example 5:
Input: "abbbabbbcabbbabbbc" Output: "2[2[abbb]c]" Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".
Companies:
Google
Related Topics:
Dynamic Programming
Similar Questions:
TLE Solution
The TLE case "slkjdfbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb".
Why not simply traverse the string and merge substring of the same letters? Because for this case "aaabaaaaaabaaa", the result should be "2[aaabaaa]". If we merge it to "aaab6[a]baaa", we can’t get the right answer.
// OJ: https://leetcode.com/problems/encode-string-with-shortest-length/
// Time: O(N^3)
// Space: O(N)
class Solution {
private:
bool compare(string &s, int s1, int s2, int len) {
if (s1 + len > s.size() || s2 + len > s.size()) return false;
int i = 0;
for (; i < len && s[s1 + i] == s[s2 + i]; ++i);
return i == len;
}
public:
string encode(string s) {
if (s.size() <= 4) return s;
string ans = s;
for (int len = s.size() / 2; len >= 1; --len) {
for (int i = 0; i + len <= s.size(); ++i) {
int cnt = 1;
while (compare(s, i, i + cnt * len, len)) ++cnt;
if (cnt == 1) continue;
string prefix = i > 0 ? encode(s.substr(0, i)) : "";
string suffix = i + cnt * len < s.size() ? encode(s.substr(i + cnt * len)) : "";
string middle = to_string(cnt) + "[" + encode(s.substr(i, len)) + "]";
string encoded = prefix + middle + suffix;
if (ans == "" || encoded.size() < ans.size()) ans = encoded;
}
}
return ans;
}
};
-
class Solution { public String encode(String s) { int length = s.length(); String[][] dp = new String[length][length]; for (int i = length - 1; i >= 0; i--) { for (int j = i; j < length; j++) { int curLength = j - i + 1; String substring = s.substring(i, j + 1); if (curLength <= 4) dp[i][j] = substring; else { int subLength = (substring + substring).indexOf(substring, 1); if (subLength < curLength) dp[i][j] = String.valueOf(curLength / subLength) + "[" + dp[i][i + subLength - 1] + "]"; else { dp[i][j] = substring; for (int k = i; k < j; k++) { if ((dp[i][k] + dp[k + 1][j]).length() < dp[i][j].length()) dp[i][j] = dp[i][k] + dp[k + 1][j]; } } } } } return dp[0][length - 1]; } } -
// OJ: https://leetcode.com/problems/encode-string-with-shortest-length/ // Time: O(N^3) // Space: O(N) class Solution { private: bool compare(string &s, int s1, int s2, int len) { if (s1 + len > s.size() || s2 + len > s.size()) return false; int i = 0; for (; i < len && s[s1 + i] == s[s2 + i]; ++i); return i == len; } public: string encode(string s) { if (s.size() <= 4) return s; string ans = s; for (int len = s.size() / 2; len >= 1; --len) { for (int i = 0; i + len <= s.size(); ++i) { int cnt = 1; while (compare(s, i, i + cnt * len, len)) ++cnt; if (cnt == 1) continue; string prefix = i > 0 ? encode(s.substr(0, i)) : ""; string suffix = i + cnt * len < s.size() ? encode(s.substr(i + cnt * len)) : ""; string middle = to_string(cnt) + "[" + encode(s.substr(i, len)) + "]"; string encoded = prefix + middle + suffix; if (ans == "" || encoded.size() < ans.size()) ans = encoded; } } return ans; } }; -
class Solution(object): def encode(self, s, dp={}): """ :type s: str :rtype: str """ if len(s) < 5: return s elif s in dp: return dp[s] dp[s] = s idx = (2 * s).find(s, 1) if 0 <= idx < len(s): dp[s] = str(len(s) / idx) + "[" + self.encode(s[:idx], dp) + "]" for i in range(1, len(s)): left = self.encode(s[:i], dp) right = self.encode(s[i:], dp) if len(left) + len(right) < len(dp[s]): dp[s] = left + right return dp[s] -
func encode(s string) string { n := len(s) f := make([][]string, n) for i := range f { f[i] = make([]string, n) } g := func(i, j int) string { t := s[i : j+1] if len(t) < 5 { return t } k := strings.Index((t + t)[1:], t) + 1 if k < len(t) { cnt := len(t) / k return strconv.Itoa(cnt) + "[" + f[i][i+k-1] + "]" } return t } for i := n - 1; i >= 0; i-- { for j := i; j < n; j++ { f[i][j] = g(i, j) if j-i+1 > 4 { for k := i; k < j; k++ { t := f[i][k] + f[k+1][j] if len(t) < len(f[i][j]) { f[i][j] = t } } } } } return f[0][n-1] } -
function encode(s: string): string { const n = s.length; const f: string[][] = new Array(n).fill(0).map(() => new Array(n).fill('')); const g = (i: number, j: number): string => { const t = s.slice(i, j + 1); if (t.length < 5) { return t; } const k = t.repeat(2).indexOf(t, 1); if (k < t.length) { const cnt = Math.floor(t.length / k); return cnt + '[' + f[i][i + k - 1] + ']'; } return t; }; for (let i = n - 1; i >= 0; --i) { for (let j = i; j < n; ++j) { f[i][j] = g(i, j); if (j - i + 1 > 4) { for (let k = i; k < j; ++k) { const t = f[i][k] + f[k + 1][j]; if (t.length < f[i][j].length) { f[i][j] = t; } } } } } return f[0][n - 1]; }