Leetcode-514【自由之路】-隐马尔科夫模型

本文主要是介绍Leetcode-514【自由之路】-隐马尔科夫模型，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

输入: ring = "godding", key = "gd"
输出: 4
解释:
 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
 当然, 我们还需要1步进行拼写。
 因此最终的输出是 4。

C++代码如下：

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        vector<int> m[26];
        int n1 = ring.size();
        int n2 = key.size();
        for (int i = 0; i < n1; i++) {
            m[ring[i] - 'a'].push_back(i);
        }
        vector<vector<int>> dp(key.size(), vector<int>(ring.size(), INT_MAX));
        for (int j: m[key[0] - 'a']) {
            dp[0][j] = min(j, n1 - j) + 1;
        }
        for (int i = 1; i < n2; i++) {
            int pos = key[i] - 'a';
            for (int j : m[pos]) {
                for (int k = 0; k < n1; k++) {
                    if (dp[i - 1][k] != INT_MAX) {
                        int a = min(j, k);
                        int b = max(j, k);
                        dp[i][j] = min(dp[i][j], dp[i - 1][k] + min(b - a, n1 + a - b) + 1);
                    }
                }
            }
        }
        int result = INT_MAX;
        for (int i: m[key[n2 - 1] - 'a']) {
            result = min(result, dp[n2 - 1][i]);
        }
        return result;
    }
};

这篇关于Leetcode-514【自由之路】-隐马尔科夫模型的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！