указать строку s, закодировать ее в формате: «aaa» to «3 [a]». Длина закодированной строки должна быть самой короткой. пример: "abbabb" на "2 [a2 [б]]"Кодировать строку «aaa» до «3 [a]»
обновление: предположим, что строка содержит только строчные буквы
обновление: вот мой код в C++, но это медленно. Я знаю, что одним из улучшений является использование KMP для вычисления, если текущая строка объединяется повторяющейся строкой.
// this function is used to check if a string is combined by repeating a substring.
// Also Here can be replaced by doing KMP algorithm for whole string to improvement
bool checkRepeating(string& s, int l, int r, int start, int end){
if((end-start+1)%(r-l+1) != 0)
return false;
int len = r-l+1;
bool res = true;
for(int i=start; i<=end; i++){
if(s[(i-start)%len+l] != s[i]){
res = false;
break;
}
}
return res;
}
// this function is used to get the length of the current number
int getLength(int l1, int l2){
return (int)(log10(l2/l1+1)+1);
}
string shortestEncodeString(string s){
int len = s.length();
vector< vector<int> > res(len, vector<int>(len, 0));
//Initial the matrix
for(int i=0; i<len; i++){
for(int j=0; j<=i; j++){
res[j][i] = i-j+1;
}
}
unordered_map<string, string> record;
for(int i=0; i<len; i++){
for(int j=i; j>=0; j--){
string temp = s.substr(j, i-j+1);
/* if the current substring has showed before, then no need to compute again
* Here is a example for this part: if the string is "abcabc".
* if we see the second "abc", then no need to compute again, just use the
* result from first "abc".
**/
if(record.find(temp) != record.end()){
res[j][i] = record[temp].size();
continue;
}
string ans = temp;
for(int k=j; k<i; k++){
string str1 = s.substr(j, k-j+1);
string str2 = s.substr(k+1, i-k);
if(res[j][i] > res[j][k] + res[k+1][i]){
res[j][i] = res[j][k]+res[k+1][i];
ans = record[str1] + record[str2];
}
if(checkRepeating(s, j, k, k+1, i) == true && res[j][i] > 2+getLength(k-j+1, i-k)+res[j][k]){
res[j][i] = 2+getLength(k-j+1, i-k)+res[j][k];
ans = to_string((i-j+1)/(k-j+1)) + '[' + record[str1] +']';
}
}
record[temp] = ans;
}
}
return record[s];
}
Я пытался жадным решением. но сложность очень плохая. Попробуйте строку из индекса 0 с длиной 1,2,3 ... и затем найдите индекс, который эта подстрока не повторит, а затем вызовите функцию с остальной частью строки. а также сделать то же самое префиксную строку с len 1, 2, 3 ... – NHa
Хорошо, отредактируйте свой код в вопросе, если вы хотите, чтобы кто-то помог вам устранить его. –