[LeetCode]Freedom Trail

这道题贪婪肯定是不行的，很容易举出反例。Brute force的方法就是递归所有的可能性，比如key是abc的话，我们先找到从当前index到所有a的步数，对于每个a顺时针逆时针取较小的。下一层是b然后c，依次类推，所有结果中取最小的。显而易见有很多重复的计算，我们用memorization优化。这也给了我们dp的思路，类似的，我们用dp[i][j]表示·匹配key的前i个char之后，停在ring的j位置所需要的移动距离(我们暂时不需要考虑match所对应的那一步，在结果上加key.size()即可)，假设ring长度为n，key长度m，我们有递推公式：

• dp[i][j] = min(dp[i - 1][k] + min(dist, n - dist))，其中k为所有使得ring[k] == key[i - 2]成立的位置，dist = abs(j - k)
• 我们只关心满足条件key[i - 1] == ring[j]的dp[i][j]的数值，显然，当我们匹配了前i个char之后，肯定是停ring中和key[i - 1]一样的char上，这就是对应的最小距离，不需要再移动了。对于不一样的char，我们根本不需要考虑。
• 我们return的值，就是max(dp[m][k]) + m，k满足条件ring[k] = key[m - 1]。dp只代表移动的距离，我们还要加上match的步骤，总共是m

假设key长度为m，ring长度为n，时间复杂度为O(m^2 * n)，空间复杂度O(m * n)：

我们可以用滚动数组把空间优化到O(n):

当然dp方程不止一种，我们还可以用dp[i][j]表示从ring中位于j的string开始匹配key[i:]所需要的最小移动距离，我们有递归公式：

• dp[i][j] = min(dp[i + 1][k] + min(dist, n - dist))，k满足条件ring[k] = key[i]，dist = abs(j - k)
• 我们要求的值就是dp[0][0] + m

时间复杂度为O(m^2 * n)，空间复杂度可以优化到O(n)，代码如下：