从数字数组中查找可能的字母串数

Question

给定一个字符串12345和字母像数的映射 a =1,b =2.., ,,y=25 z=26编写代码以查找给定字符串中可能的字母串数.

Ex字符串12345具有可能的字母字符串,如{lcde,awde, abcde}映射所示{12-3-4-5, 1-23-4-5, 1-2-3-4-5}.

我对如何做到这一点有一个大概的了解.我想这会是递归的.查看第一个数字并将其char映射添加到结果中,然后使用子数组(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.

细节：

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