字符串的字母数字缩写

给定一个长度小于10的字符串, 我们需要打印该字符串的所有字母数字缩写。

字母数字缩写形式为字符与数字混合的形式, 该数字等于所选子字符串的跳过字符数。因此, 每当将跳过字符的子字符串, 你必须将其替换为表示子字符串中字符数的数字。字符串中可以有任意多个跳过的子字符串。没有两个子字符串彼此相邻。因此, 结果中没有两位数字相邻。有关更清晰的主意, 请参见示例。

例子：

Input : ANKS 
Output :
ANKS (nothing is replaced)
ANK1 (S is replaced) 
AN1S (K is replaced)
AN2  (KS is replaced)
A1KS (N is replaced)
A1K1 (N and S are replaced)
A2S (NK is replaced)
A3 (NKS is replaced)
1NKS (A is replaced)
1NK1 (A and S are replaced)
1N1S (A and N is replaced)
1N2 (A and KS are replaced)
2KS (AN is replaced)
2K1 (AN and S is replaced)
3S (ANK is replaced)
4 (ANKS is replaced)

Input : ABC
Output : 
ABC
AB1 
A1C 
A2 
1BC 
1B1 
2C 
3
Note: 11C is not valid because no two digits should be adjacent, 2C is the correct one because AB is a substring, not A and B individually

资源：Google面试问题

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

想法是从空字符串开始。在每一步中, 我们都有两个选择。

按原样考虑字符。
添加字符进行计数。如果没有计数, 请使用1。

你可以看到每个字符如何以字符或数字的形式累加到结果中。这进一步在末尾引起2 ^ n缩写, 其中n是字符串的长度。

// C++ program to print all Alpha-Numeric Abbreviations
// of a String
#include <bits/stdc++.h>
using namespace std;
  
// Recursive function to print the valid combinations
// s is string, st is resultant string
void printCompRec( const string& s, int index, int max_index, string st)
{
     // if the end of the string is reached
     if (index == max_index) {
         cout << st << "\n" ;
         return ;
     }
  
     // push the current character to result
     st.push_back(s[index]);
  
     // recur for the next [Using Char]
     printCompRec(s, index + 1, max_index, st);
  
     // remove the character from result
     st.pop_back();
  
     // set count of digits to 1
     int count = 1;
  
     // addition the adjacent digits
     if (!st.empty()) {
  
         if ( isdigit (st.back())) {
  
             // get the digit and increase the count
             count += ( int )(st.back() - '0' );
  
             // remove the adjacent digit
             st.pop_back();
         }
     }
  
     // change count to a character
     char to_print = ( char )(count + '0' );
  
     // add the character to result
     st.push_back(to_print);
  
     // recur for this again [Using Count]
     printCompRec(s, index + 1, max_index, st);
}
  
// Wrapper function
void printComb(std::string s)
{
     // if the string is empty
     if (!s.length())
         return ;
  
     // Stores result strings one one by one
     string st;
  
     printCompRec(s, 0, s.length(), st);
}
  
// driver function
int main()
{
     string str = "GFG" ;
     printComb(str);
     return 0;
}

输出如下：