在这里，我们将看到一个与给定字符串的字母数字缩写相关的有趣问题。字符串长度小于10。我们将打印出所有的字母数字缩写。
字母数字缩写是由字符和数字混合形成的。该数字的值是被省略的字符数。可能有任意数量的被省略的子字符串。没有两个子字符串是相邻的。让我们看一下获取这个概念的算法。
算法
printAbbreviation(s, index, max, str) −
begin
if index is same as max, then
print str
end if
add s[index] at the last of str
printAbbreviation(s, index + 1, max, str)
delete last character from str
count := 1
if str is not empty, then
if the last character of str is a digit, then
add last digit with the count value
delete last character from str
end if
end if
add count after the str
printAbbreveation(s, index + 1, max, str)
end示例
#include <iostream>
using namespace std;
void printAbbreviation(const string& s, int index, int max_index, string str) {
if (index == max_index) { //if string has ended
cout << str << endl;
return;
}
str.push_back(s[index]); // push the current character to result
printAbbreviation(s, index + 1, max_index, str); //print from next index
str.pop_back(); //remove last character
int count = 1;
if (!str.empty()) {
if (isdigit(str.back())) { //if the last one is digit, then
count += (int)(str.back() - '0'); //count the integer value of that digit
str.pop_back(); //remove last character
}
}
char to_char = (char)(count + '0'); //make count to character
str.push_back(to_char);
printAbbreviation(s, index + 1, max_index, str); //do for next index
}
void printCombination(string str) {
if (!str.length()) //if the string is empty
return;
string str_res;
printAbbreviation(str, 0, str.length(), str_res);
}
int main() {
string str = "HELLO";
printCombination(str);
}输出
HELLO HELL1 HEL1O HEL2 HE1LO HE1L1 HE2O HE3 H1LLO H1LL1 H1L1O H1L2 H2LO H2L1 H3O H4 1ELLO 1ELL1 1EL1O 1EL2 1E1LO 1E1L1 1E2O 1E3 2LLO 2LL1 2L1O 2L2 3LO 3L1 4O 5
