Related: LeetCode 394 - Decode String
http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/
https://discuss.leetcode.com/topic/71963/accepted-solution-in-java
X.
http://www.cnblogs.com/grandyang/p/6194403.html
我们建立一个二维的DP数组，其中dp[i][j]表示s在[i, j]范围内的字符串的缩写形式(如果缩写形式长度大于子字符串，那么还是保留子字符串)，那么如果s字符串的长度是n，最终我们需要的结果就保存在dp[0][n-1]中，然后我们需要遍历s的所有子字符串，对于任意一段子字符串[i, j]，我们我们以中间任意位置k来拆分成两段，比较dp[i][k]加上dp[k+1][j]的总长度和dp[i][j]的长度，将长度较小的字符串赋给dp[i][j]，
然后我们要做的就是在s中取出[i, j]范围内的子字符串t进行合并。合并的方法是我们在取出的字符串t后面再加上一个t，然后在这里面寻找子字符串t的第二个起始位置，如果第二个起始位置小于t的长度的话，说明t包含重复字符串，举个例子吧，比如 t = "abab", 那么t+t = "abababab"，我们在里面找第二个t出现的位置为2，小于t的长度4，说明t中有重复出现，重复的个数为t.size()/pos = 2个，那么我们就要把重复的地方放入中括号中，注意中括号里不能直接放这个子字符串，而是应该从dp中取出对应位置的字符串，因为重复的部分有可能已经写成缩写形式了，比如题目中的例子5。如果t = "abc"，那么t+t = "abcabc"，我们在里面找第二个t出现的位置为3，等于t的长度3，说明t中没有重复出现，那么replace就还是t。然后我们比较我们得到的replace和dp[i][j]中的字符串长度，把长度较小的赋给dp[i][j]即可，时间复杂度为O(n3)，空间复杂度为O(n2)，
https://segmentfault.com/a/1190000008341304
http://bookshadow.com/weblog/2016/12/11/leetcode-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:
Example 2:
Example 3:
Example 4:
Example 5:
https://chenboxie.wordpress.com/2018/07/08/leetcode-471-encode-string-with-shortest-length/
区间DP的问题，我们用dp[i][j]表示子串s[i:j]的最小压缩串，我们有如下递推方程：
- dp[i][j] = min(dp[i][k] + dp[k + 1][j]), where 1 <= k < j, ‘+’ means concatenate here
- dp[i][j] = min(dp[i][j], compress(s[i:j])), compress is a function to find if we can shorten input string by find a repeating pattern in itself
这里两个递推公式，第一个递推适用于 abcabcd这种string，在k = 5的时候, dp(abcabcd) = dp(abcabc) + dp(d) = 2[abc] + d = 2[abc]d
2. 但仅仅使用第一个递推是不够的，例如这个例子，abcabcabc, 用第一个递推公式可以得到, dp(abcabcabc) = dp(abcabc) + dp(abc) = 2[abc] + abc = 2[abc]abc，永远无法得到3[abc]
2. 但仅仅使用第一个递推是不够的，例如这个例子，abcabcabc, 用第一个递推公式可以得到, dp(abcabcabc) = dp(abcabc) + dp(abc) = 2[abc] + abc = 2[abc]abc，永远无法得到3[abc]
所以由此我们需要第二个递推：
这里compress的功能是，找到string自身的重复串来压缩string。比如对于abcabcabc，我们只进行区间dp是没有办法找到3[abc]的，所以我们必须对自身进行compress。
这里就引出很重要的一个技巧：
我们在字符串t后面再加上一个t，然后在这里面寻找子字符串t的第二个起始位置，如果第二个起始位置小于t的长度的话，说明t包含重复字符串，举个例子吧，比如 t = “abab”, 那么t+t = “abababab”，我们在里面找第二个t出现的位置为2，小于t的长度4，说明t中有重复出现，重复的个数为t.size()/pos = 2个
这里compress的功能是，找到string自身的重复串来压缩string。比如对于abcabcabc，我们只进行区间dp是没有办法找到3[abc]的，所以我们必须对自身进行compress。
这里就引出很重要的一个技巧：
我们在字符串t后面再加上一个t，然后在这里面寻找子字符串t的第二个起始位置，如果第二个起始位置小于t的长度的话，说明t包含重复字符串，举个例子吧，比如 t = “abab”, 那么t+t = “abababab”，我们在里面找第二个t出现的位置为2，小于t的长度4，说明t中有重复出现，重复的个数为t.size()/pos = 2个
3. 假设自身的字符串为sub, 在对自身进行压缩的过程中，如果自身是符合压缩条件的，压缩必须写成：
sub = sub.length() / index + “[” + dp[i][i + index – 1] + “]”;
举个例子，比如
sub = “abcdbcd abcdbcd”，不能写成2[abcdbcd], 而是写成2[a2[bcd]]
sub = sub.length() / index + “[” + dp[i][i + index – 1] + “]”;
举个例子，比如
sub = “abcdbcd abcdbcd”，不能写成2[abcdbcd], 而是写成2[a2[bcd]]
总结：
1. 区间DP的辨别和运用，dp[i][j] = max/min(dp[i][k] + dp[k + 1][j])
2. 像s=abcabc这样的字符串，在O(n)时间内进行压缩的方法，就是在s + s中寻找s的第二个起始位置，如果第二个起始位置小于s的长度的话，说明s包含重复字符串。
1. 区间DP的辨别和运用，dp[i][j] = max/min(dp[i][k] + dp[k + 1][j])
2. 像s=abcabc这样的字符串，在O(n)时间内进行压缩的方法，就是在s + s中寻找s的第二个起始位置，如果第二个起始位置小于s的长度的话，说明s包含重复字符串。
这道题还是应该用动态规划来做。我们建立一个二维的DP数组，其中dp[i][j]表示s在[i, j]范围内的字符串的缩写形式(如果缩写形式长度大于子字符串，那么还是保留子字符串)，那么如果s字符串的长度是n，最终我们需要的结果就保存在dp[0][n-1]中，然后我们需要遍历s的所有子字符串，对于任意一段子字符串[i, j]，我们我们以中间任意位置k来拆分成两段，比较dp[i][k]加上dp[k+1][j]的总长度和dp[i][j]的长度，将长度较小的字符串赋给dp[i][j]，然后我们要做的就是在s中取出[i, j]范围内的子字符串t进行合并。合并的方法是我们在取出的字符串t后面再加上一个t，然后在这里面寻找子字符串t的第二个起始位置，如果第二个起始位置小于t的长度的话，说明t包含重复字符串，举个例子吧，比如 t = "abab", 那么t+t = "abababab"，我们在里面找第二个t出现的位置为2，小于t的长度4，说明t中有重复出现，重复的个数为t.size()/pos = 2个，那么我们就要把重复的地方放入中括号中，注意中括号里不能直接放这个子字符串，而是应该从dp中取出对应位置的字符串，因为重复的部分有可能已经写成缩写形式了，比如题目中的例子5。如果t = "abc"，那么t+t = "abcabc"，我们在里面找第二个t出现的位置为3，等于t的长度3，说明t中没有重复出现，那么replace就还是t。然后我们比较我们得到的replace和dp[i][j]中的字符串长度，把长度较小的赋给dp[i][j]即可，时间复杂度为O(n3)，空间复杂度为O(n2)。
这里compress的功能是，找到string自身的重复串来压缩string。比如对于abcabcabc，我们只进行区间dp是没有办法找到3[abc]的，所以我们必须对自身进行compress。对自身进行压缩的就是寻找自身最小覆盖子串的过程。有多个覆盖子串我们肯定是取最小的，对于d[str]的形式，如果我们double str的长度最多也就使得d减少一位，所以str越短越好。
时间复杂度O(n^3)，寻找自身最小覆盖子串需要线性时间，代码如下：
We will form 2-D array of Strings.
dp[i][j] = string from index i to index j in encoded form.
dp[i][j] = string from index i to index j in encoded form.
We can write the following formula as:-
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) or if we can find some pattern in string from i to j which will result in more less length.
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) or if we can find some pattern in string from i to j which will result in more less length.
Time Complexity = O(n^3)
Time Complexity is O(N^4), replaceAll() is O(N) 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);
// Checking if string length < 5. In that case, we know that encoding will not help.
if(j - i < 4) {
dp[i][j] = substr;
} else {
dp[i][j] = substr;
// Loop for trying all results that we get after dividing the strings into 2 and combine the results of 2 substrings
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];
}
}
// Loop for checking if string can itself found some pattern in it which could be repeated.
for(int k=0;k<substr.length();k++) {
String repeatStr = substr.substring(0, k+1);
if(repeatStr != null
&& substr.length()%repeatStr.length() == 0
&& substr.replaceAll(repeatStr, "").length() == 0) {
String ss = substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]";
if(ss.length() < dp[i][j].length()) {
dp[i][j] = ss;
}
}
}
}
}
}
return dp[0][s.length()-1];
}X.
http://www.cnblogs.com/grandyang/p/6194403.html
我们建立一个二维的DP数组，其中dp[i][j]表示s在[i, j]范围内的字符串的缩写形式(如果缩写形式长度大于子字符串，那么还是保留子字符串)，那么如果s字符串的长度是n，最终我们需要的结果就保存在dp[0][n-1]中，然后我们需要遍历s的所有子字符串，对于任意一段子字符串[i, j]，我们我们以中间任意位置k来拆分成两段，比较dp[i][k]加上dp[k+1][j]的总长度和dp[i][j]的长度，将长度较小的字符串赋给dp[i][j]，
然后我们要做的就是在s中取出[i, j]范围内的子字符串t进行合并。合并的方法是我们在取出的字符串t后面再加上一个t，然后在这里面寻找子字符串t的第二个起始位置，如果第二个起始位置小于t的长度的话，说明t包含重复字符串，举个例子吧，比如 t = "abab", 那么t+t = "abababab"，我们在里面找第二个t出现的位置为2，小于t的长度4，说明t中有重复出现，重复的个数为t.size()/pos = 2个，那么我们就要把重复的地方放入中括号中，注意中括号里不能直接放这个子字符串，而是应该从dp中取出对应位置的字符串，因为重复的部分有可能已经写成缩写形式了，比如题目中的例子5。如果t = "abc"，那么t+t = "abcabc"，我们在里面找第二个t出现的位置为3，等于t的长度3，说明t中没有重复出现，那么replace就还是t。然后我们比较我们得到的replace和dp[i][j]中的字符串长度，把长度较小的赋给dp[i][j]即可，时间复杂度为O(n3)，空间复杂度为O(n2)，
string encode(string s) { int n = s.size(); vector<vector<string>> dp(n, vector<string>(n, "")); for (int step = 1; step <= n; ++step) { for (int i = 0; i + step - 1 < n; ++i) { int j = i + step - 1; dp[i][j] = s.substr(i, step); for (int k = i; k < j; ++k) { string left = dp[i][k], right = dp[k + 1][j]; if (left.size() + right.size() < dp[i][j].size()) { dp[i][j] = left + right; } } string t = s.substr(i, j - i + 1), replace = ""; auto pos = (t + t).find(t, 1); if (pos >= t.size()) replace = t; else replace = to_string(t.size() / pos) + '[' + dp[i][i + pos - 1] + ']'; if (replace.size() < dp[i][j].size()) dp[i][j] = replace; } } return dp[0][n - 1]; }
我们可以优化上面的方法。如果t是重复的，是不是就不需要再看left.size() + right.size() < dp[i][j].size()了。例如t是abcabcabcabcabc, 最终肯定是5[abc]，不需要再看3[abc]+abcabc或者abcabc+3[abc]。对于一个本身就重复的字符串，最小的长度肯定是n[REPEATED]，不会是某个left+right。所以应该把k的那个循环放在t和replace那部分代码的后面。这样的确提高了一些运算效率的
string encode(string s) { int n = s.size(); vector<vector<string>> dp(n, vector<string>(n, "")); for (int step = 1; step <= n; ++step) { for (int i = 0; i + step - 1 < n; ++i) { int j = i + step - 1; dp[i][j] = s.substr(i, step); string t = s.substr(i, j - i + 1), replace = ""; auto pos = (t + t).find(t, 1); if (pos < t.size()) { replace = to_string(t.size() / pos) + "[" + dp[i][i + pos - 1] + "]"; if (replace.size() < dp[i][j].size()) dp[i][j] = replace; continue; } for (int k = i; k < j; ++k) { string left = dp[i][k], right = dp[k + 1][j]; if (left.size() + right.size() < dp[i][j].size()) { dp[i][j] = left + right; } } } } return dp[0][n - 1]; }
dpi表示s[i, j]最短的压缩结果，subproblem里面枚举切分点k，分别得到dpi和dpk+1求和，找到长度最短的。
这道题关键是找sub = abcabc这种可压缩的情况，其中sub = s[i,j]。方法比较巧妙，用sub+sub = abcabcabcabc，找第二个s在s+s里出现的位置，如果不是len(sub)，则说明sub有重复，那么就要压缩这个sub，重复次数是len(sub) / indexOf(sub, 1)，重复的string用的是之前压缩过的dpi，index = indexOf(sub, 1)。
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];
}
Initially I think of 1D DP, dp[i] stands for the shortest string of first i characters, then:
dp[i] = minLen{dp[k] + encode(substring(k+1, i))}
then I realize that the second part encode(substring(k+1, i)) is actually the same with our dp problem. So it turns out the transfer function is
dp[i] = minLen{dp[k] + dp(substring(k+1, i))}
then 1D is not enough, I introduce the second dimension, which indicates the end. dp[i][j] is the shortest encoded string from i to j
But the hardest part of this problem is how to generate dp[i][j] from dp[i][k] and dp[k+1][j]
I‘ve thought about the cases like:
dp[i][k] = 3[abc] dp[k+1][j] = 2[abc], then dp[i][j] = 5[abc]
dp[i][k] = 3[abc] dp[k+1][j] = xyz, then dp[i][j] = 3[abc]xyz
dp[i][k] = aabc dp[k+1][j] = aabc, then dp[i][j] = 2[aabc]
No idea what to implement this conveniently, so refer to idea
The idea is to firstly concantenate dp[i][k] and dp[k+1][j] directly to construct dp[i][j], and then check if there exist possible repeat patterns in the original substring s.substring(i, j+1) that could further shorten dp[i][j]
replaceAll function is really clever
https://hbisheng.gitbooks.io/leetcode-google/content/471-encode-string-with-shortest-length.html
https://yijiajin.github.io/leetcode/2017/01/02/LC471.-Encode-String-with-Shortest-Length/
记忆化搜索
def __init__(self):
self.dp = dict()
def encode(self, s):
"""
:type s: str
:rtype: str
"""
size = len(s)
if size <= 1: return s
if s in self.dp: return self.dp[s]
ans = s
for p in range(1, size + 1):
left, right = s[:p], s[p:]
t = self.solve(left) + self.encode(right)
if len(t) < len(ans): ans = t
self.dp[s] = ans
return ans
def solve(self, s):
ans = s
size = len(s)
for x in range(1, size / 2 + 1):
if size % x or s[:x] * (size / x) != s: continue
y = str(size / x) + '[' + self.encode(s[:x]) + ']'
if len(y) < len(ans): ans = y
return anshttps://yijiajin.github.io/leetcode/2017/01/02/LC471.-Encode-String-with-Shortest-Length/
利用KMP算法来寻找和判断是否存在重复的子串是比较快的。顺便这是LC459题。
public String encode(String s) {
// dp solution, for each substring of s, check whether it can be encode
// dp[i][j] means substing of [i, j] after encode
if(s == null || s.length() <= 4) return s;
int len = s.length();
String[][] dp = new String[len][len];
for(int sublen = 0; sublen < len; sublen++){
for(int begin = 0; begin < len - sublen; begin++){
int end = begin + sublen;
String sub = s.substring(begin, end + 1);
dp[begin][end] = sub;
if(sublen < 4) continue; // sub.length = sublen + 1
// get shortest substring combination
for(int i = begin; i < end; i++){
if(dp[begin][i].length() + dp[i+1][end].length() < dp[begin][end].length())
dp[begin][end] = dp[begin][i] + dp[i+1][end];
}
// if repeat, using kmp to encode then compare with shortest combination
String pattern = kmp(sub);
//System.out.println(pattern);
// no repeat, keep origional -> shorest combination
if(pattern.length() == sub.length()) continue;
// find repeat, repeat should also be encoded
String encode = sub.length()/pattern.length() + "[" + dp[begin][begin+pattern.length()-1] + "]";
if(encode.length() < dp[begin][end].length()) dp[begin][end] = encode;
} // for begin
} // for sublen
return dp[0][len - 1];
} // code
// kmp method to find repeat pattern in one String
private String kmp(String str){
int len = str.length();
int[] next = new int[len];
char[] arr = str.toCharArray();
Arrays.fill(next, -1);
int i = 0, j = 1;
for(; j < len; j++){
i = next[j - 1];
while(arr[i + 1] != arr[j] && i >= 0) i = next[i];
if(arr[i + 1] == arr[j]) next[j] = i + 1;
else next[j] = -1;
}
//System.out.println(Arrays.toString(next));
// if repeat, it must before the 0
int patternLen = len - next[len - 1] - 1;
if(patternLen == 0) return str;
if(patternLen != len && len % patternLen == 0) {
return str.substring(0, patternLen);
} else {
return str;
}
} // kmp
