时间优化 C++ 函数以找到解码可能性的数量

Question

这是一个 interview practice problem from CodeFights。我有一个有效的解决方案，除了对于非常大的输入运行花费的时间太长。

问题描述（来自上面的link）

包含从 'A' 到 'Z' 的大写字母的绝密 message 已使用以下映射编码为数字：

'A' -> 1
'B' -> 2
...
'Z' -> 26

您是一名 FBI 特工，您需要确定可以对消息进行解码的方式总数。

因为答案可能非常大，所以取模 10^9 + 7。

例子

对于message = "123"，输出应该是

mapDecoding(message) = 3.

"123"可以解码为"ABC"(1 2 3)、"LC"(12 3)或"AW"(1 23)，所以总方式数是 3.

Input/Output

[时间限制] 500ms (cpp)

[输入]字符串消息

只包含数字的字符串。

保证约束：

0 ≤ message.length ≤ 105.

[输出]整数

解码给定消息的方法总数。

到目前为止我的解决方案

我们要在一个函数中实现解决方案int mapDecoding(std::string message)，所以我的整个解决方案如下：

/*0*/ void countValidPaths(int stIx, int endIx, std::string message, long *numPaths)
/*1*/ {
/*2*/    //check out-of-bounds error
/*3*/    if (endIx >= message.length())
/*4*/        return;
/*5*/    
/*6*/    int subNum = 0, curCharNum;
/*7*/    //convert substr to int
/*8*/    for (int i = stIx; i <= endIx; ++i)
/*9*/    {
/*10*/       curCharNum = message[i] - '0';
/*11*/       subNum = subNum * 10 + curCharNum;
/*12*/   }
/*13*/    
/*14*/   //check for leading 0 in two-digit number, which would not be valid
/*15*/   if (endIx > stIx && subNum < 10)
/*16*/       return;
/*17*/    
/*18*/   //if number is valid
/*19*/   if (subNum <= 26 && subNum >= 1)
/*20*/   {
/*21*/       //we've reached the end of the string with success, therefore return a 1
/*22*/       if (endIx == (message.length() - 1) )
/*23*/           ++(*numPaths);
/*24*/       //branch out into the next 1- and 2-digit combos
/*25*/       else if (endIx == stIx)
/*26*/       {
/*27*/           countValidPaths(stIx, endIx + 1, message, numPaths);
/*28*/           countValidPaths(stIx + 1, endIx + 1, message, numPaths);
/*29*/       }
/*30*/       //proceed to the next digit
/*31*/       else
/*32*/            countValidPaths(endIx + 1, endIx + 1, message, numPaths);
/*33*/   }
/*34*/ }    
/*35*/
/*36*/ int mapDecoding(std::string message) 
/*37*/ {
/*38*/    if (message == "")
/*39*/        return 1;
/*40*/    long numPaths = 0;
/*41*/    int modByThis = static_cast<int>(std::pow(10.0, 9.0) + 7);
/*42*/    countValidPaths(0, 0, message, &numPaths);
/*43*/    return static_cast<int> (numPaths % modByThis);
/*44*/ }

问题

我已经通过了 11/12 的 CodeFight 初始测试用例，例如mapDecoding("123") = 3 和 mapDecoding("11115112112") = 104。但是，最后一个测试用例有message = "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211"，我的程序执行时间太长：

Expected_output:      782204094
My_program_output:    <empty due to timeout>

我把 countValidPaths() 写成一个递归函数，它的递归调用在第 27、28 和 32 行。我可以看到这么大的输入会导致代码花费这么长时间，但是我'我绞尽脑汁想找出更有效的解决方案来涵盖所有可能的组合。

因此，百万美元的问题：你有什么建议来优化我当前的程序，以便运行的时间大大减少？

Answer 1

一些建议。首先，这个问题可能可以表述为动态规划问题。它对我来说有那种气味。你一遍又一遍地计算同样的东西。

第二个是“1"s and "2"s are a Fibonacci sequence in terms of the number of possibilities. Any other value terminates the sequence. So you can split the strings into runs of of ones and twos terminated by any other number. You will need special logic for a termination of zero since it does not also correspond to a character. So split the strings count, the length of each segment, look up the fibonacci number (which can be pre-computed) and multiply the values. So your example "11115112112”的长连续序列产生“11115”和“112112”以及 f(5) = 8 和 f(6) = 13, 8*13 = 104.

您的长字符串是 1 和 2 的序列，长度为 100 位。下面的Java（对不起，我的C++生疏了）程序通过这种方法正确计算了它的值

public class FibPaths {
private static final int MAX_LEN = 105;
private static final BigInteger MOD_CONST = new BigInteger("1000000007");
private static BigInteger[] fibNum = new BigInteger[MAX_LEN];

private static void computeFibNums() {
    fibNum[0] = new BigInteger("1");
    fibNum[1] = new BigInteger("1");
    for (int i = 2; i < MAX_LEN; i++) {
        fibNum[i] = fibNum[i-2].add(fibNum[i-1]);
    }
}

public static void main(String[] argv) {
    String x = "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211";
    computeFibNums();
    BigInteger val = fibNum[x.length()].mod(MOD_CONST);
    System.out.println("N=" + x.length() + " , val = " + val);
}

}

时间优化 C++ 函数以找到解码可能性的数量

Time optimize C++ function to find number of decoding possibilities

c++

runtime

dynamic-programming

decoding

string-decoding

问题描述（来自上面的link）

例子

Input/Output

到目前为止我的解决方案

问题