Leetcode 514: Freedom Trail

https://leetcode.com/problems/freedom-trail/description/

Notes:

In principle, this question is can be solved by brute force dfs searching: the idea is simple, we just try all the possible ways, then then find the one with the shortest steps.

The theoretical upper bound time complexity is O(N*M!), where N is the length of the ring, and M is the length of the key. So the brute method can not pass the OJ.

One improvement is that we can just memorize the results with the key parameters: one is the position on the ring, and the other is the position on the key. Since these two parameter can always give one specific state of the problem, they can be used to describe the state completely.

memo[i][j] represents the shortest step to match ring[i, .. end] to key[j, ... end].

Since we can rotate either clockwise or anti-clockwise, so for each ring[x] == key[j], we need to determine which way can give us a shorter step. This is easy to do: we just need to compare the steps from both directions, and choose the smaller one.

In one word, we will apply memorization to memorize the local minimum, and then using the local minimums to find the global minimum.

The time complexity now is O(N* N*M).

See the code below:

class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int m = ring.size(), n = key.size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        return dfs(ring, 0, key, 0, memo);
    }

private:
    int dfs(string &rs, int i, string &ks, int j, vector<vector<int>>& memo) {
        if(j==ks.size()) return 0;
        if(memo[i][j] != -1) return memo[i][j];
        int temp = -1;
        for(int x=0; x<rs.size(); ++x) {
            int one_dis = 0;
            if(rs[x] == ks[j]) {
                int dis1 = abs(i - x), dis2 = (int)rs.size() - dis1;//two ways of rotation
                one_dis = min(dis1, dis2) + 1 + dfs(rs, x, ks, j+1, memo);
                if(temp == -1) temp = one_dis;
                else temp = min(temp, one_dis);
            }
        }
        return memo[i][j] = temp;
    }
};