题目描述
给定一个非空字符串,将其编码为具有最短长度的字符串。
编码规则是:k[encoded_string]
,其中在方括号encoded_string
中的内容重复k
次。
注:
k
为正整数且编码后的字符串不能为空或有额外的空格。
你可以假定输入的字符串只包含小写的英文字母。字符串长度不超过 160。
如果编码的过程不能使字符串缩短,则不要对其进行编码。如果有多种编码方式,返回任意一种即可。
样例
示例 1:
输入: "aaa"
输出: "aaa"
解释: 无法将其编码为更短的字符串,因此不进行编码。
示例 2:
输入: "aaaaa"
输出: "5[a]"
解释: "5[a]" 比 "aaaaa" 短 1 个字符。
示例 3:
输入: "aaaaaaaaaa"
输出: "10[a]"
解释: "a9[a]" 或 "9[a]a" 都是合法的编码,和 "10[a]" 一样长度都为 5。
示例 4:
输入: "aabcaabcd"
输出: "2[aabc]d"
解释: "aabc" 出现两次,因此一种答案可以是 "2[aabc]d"。
示例 5:
输入: "abbbabbbcabbbabbbc"
输出: "2[2[abbb]c]"
解释: "abbbabbbc" 出现两次,但是 "abbbabbbc" 可以编码为 "2[abbb]c",因此一种答案可以是 "2[2[abbb]c]"。
算法1
(区间动态规划) $O(n^3)$
首先得解决这么一个问题 :
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s).find(s, 1) != s.size();
}
};
进一步,假如它可以由它的一个子串重复多次构成,那么这个子串是什么,重复了多少次, 返回重复的次数?
class Solution {
public:
int repeatedSubstringPattern(string s) {
int p = (s + s).find(s, 1);
if (p != s.size())
return s.size() / p;
else
return 0;
}
};
其中p
的含义为:
- 从
s + s
下标1开始匹配s,第一次匹配的下标, - 若
p != s.szie()
, 则s[0, p -1]
为重复子串,长度为p
, 重复次数为s.size() / p
不妨验证一下
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s1 = "abab";
string s2 = "aba";
int p = (s1 + s1).find(s1, 1);
printf("%s中%s出现的下标索引为%d\n其中子串为: %s, 重复次数为 : %d\n",
(s1 + s1).c_str(), s1.c_str(), p, s1.substr(0, p).c_str(), s1.size() / p);
cout << endl;
printf("%s中%s出现的下标索引为%d \n", (s2 + s2).c_str(), s2.c_str(), (s2 + s2).find(s2, 1));
return 0;
}
输出
abababab中abab出现的下标索引为2
其中子串为: ab, 重复次数为 : 2
abaaba中aba出现的下标索引为3
f(i, j)
表示: 字符串从索引i到j处的子串的 最短长度的字符串编码
假如字符串为s, 字符串从索引i到j处的子串为 string t = s.substr(i, j - i + 1)
接下来判断t
,能否由它的一个子串重复多次构成,如果可以,则返回”次数 + [子串]“
的形式 ,如 4[ab]
其中子串的编码形式为 : f(i, i + p - 1)
枚举区间
- 枚举长度
- 枚举区间起点
- 得到区间
[i,j]
- [i,j]区间
自成一派
, 由它的一个子串重复多次构成f(i,j) = cnt + "[" + f(i, i + p -1) + "]"
- 若[i,j] 可以短的的区间编码连接而成,枚举分割点k得到
[i, k]
和[k + 1, j]
f(i, j) = f(i, j).size() > f(i,k) + f(k + 1,j).size() : f(i,k) + f(k + 1,j).size() ? f(i, j)
- [i,j]区间
- 得到区间
- 枚举区间起点
时间复杂度
- 时间复杂度 : $0(n^3)$
- 空间复杂度 : $0(n^2)$
C++ 代码
class Solution {
public:
vector<vector<string>> f;
string encode(string s) {
int n = s.size();
f = vector<vector<string>> (n, vector<string>(n));
// 区间dp 枚举长度 枚举起点
// f(i,j) 字符串子串从索引i到 j处的最短长度的字符串编码
for(int len = 1; len <= n; len ++)
for(int i = 0; i + len - 1 < n; i ++){
int j = i + len - 1;
f[i][j] = sub_str(s, i, j); // 要么是子串重复 要么是短子串的连接
if(len > 4){
for(int k = i; k < j; k ++){ // 枚举分割点[i, j] -> [i, k] [k + 1, j]
string tmp = f[i][k] + f[k + 1][j];
if(f[i][j].size() > tmp.size()) f[i][j] = tmp;
}
}
}
return f[0][n - 1];
}
string sub_str(string s, int i, int j){
s = s.substr(i, j - i + 1);
if(s.size() < 5) return s ;// 如果编码的过程不能使字符串缩短,则不要对其进行编码。 AAAA -> 4[A] 没有缩短
int p = (s + s).find(s, 1); // 返回的是下标 前面有p个数 [0, p - 1]为重复字串 重复次数为字符串长度/ p
if(p != s.size())
return to_string(s.size() / p) + "[" + f[i][i + p - 1] + "]";
else
return s;
}
};
其他
另外一种找重复子串的朴素做法 $o(n^2)$
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
// 枚举子串的长度 且该子串一定是其前缀
for(int i = 1; i * 2 <= n ; i ++){
// 首先长度满足要求
if(n % i == 0){
// 再看字符是否相同 [0, i-1] [i, 2*i - 1]
bool flag = true;
for(int j = i; j < n; j ++){
if(s[j] != s[j - i]){
flag = false;
break;
}
}
if(flag) return true;
}
}
return false;
}
};