c++ - 从数字数组中查找可能的字母字符串数

Question

Given a string 12345 and a alphabet to number mapping like a =1, b =2.., y=25, z=26; write a code to find the number of possible alphabet strings from the given string.

E.x. string 12345 has possible alphabet strings as {lcde,awde, abcde} from the mappings {12-3-4-5, 1-23-4-5, 1-2-3-4-5}.

我对如何去做有一个大概的了解。我想这将是递归的。查看第一个数字并将它的字符映射添加到结果中，然后使用子数组 (1, size - 1) 递归。还要查看前两个数字，看看它们是否 <= 26。如果是，将其添加到结果中并递归 (2, size - 2)。这样做直到数字数组为空。

虽然我卡在了实际的实现上。有比递归更聪明的方法吗？

Answer 1

这类似于断字问题。您可以使用相同的方法来解决它。您可以使用内存来减少整体运行时间。如果您在给定的示例中看到:

12-3-4-5, 1-23-4-5, 1-2-3-4-5 

4 和 5 不断重复，您要一次又一次地计算它。您可以在第一次计算时存储给定索引的排列，并在以后访问同一索引时使用它。

伪代码:

recursive_function(string,index)
 if you have already calculated values for this index in previous call
    return value

 recursive_function(string,index+1)
 if possible 
   recursive_function(string,index+2) 

 store this value for future use.

详细信息:

当你递归调用 say index i 时，当您完成此调用(基本上从当前递归返回)时，您已经使用/计算/找到所有可能的值(子字符串的所有排列从索引开始 i )。您可以存储这些值，因为如果您看到，有时您可能会再次回到索引 i从其他一些索引说 j (j<i) .所以现在你可以从这个地方本身返回，而不是对索引 i 进行更多的递归调用因为您已经计算了索引值 i不管j如何，这都是一样的