471. Encode String with Shortest Length
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]".
Solution
(1) Java
class Solution {
public String encode(String s) {
if (s.length() <= 4) {
return s;
}
int len = s.length();
String[][] dp = new String[len][len];
String[][] sd = new String[len][len];
int[][] counts = new int[len][len];
for (int l = 0; l < len; l++) {
for (int i = 0; i+l < len; i++) {
int j = i+l;
counts[i][j] = 1;
dp[i][j] = s.substring(i, j+1);
sd[i][j] = s.substring(i, j+1);
boolean found = false;
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];
}
if (!found && sd[i][k].equals(sd[k+1][j])) {
counts[i][j] = counts[i][k]+counts[k+1][j];
sd[i][j] = sd[i][k];
found = true;
}
}
if (found) {
String str = Integer.toString(counts[i][j])+"["+sd[i][j]+"]";
if (dp[i][j].length() > str.length()) {
dp[i][j] = str;
}
} else {
sd[i][j] = dp[i][j];
}
}
}
return dp[0][len-1];
}
}
(2) Python
(3) Scala