Solution by zachwen


  • 0
    Z

    Approach #1 Brute Force [Time Limit Exceeded]

    Intuition

    The very natural brute force approach is to simply try all possible paths to finish the desired key, and return the length of the shortest one.

    Algorithm

    Let the length of ring be r, and that of key be k. Since the string ring is circular, the distance between any two indices is bound by $$\floor{\frac{r}{2}}$$. The calculation of this "circular distance" is encapsulated in the helper function circularDistance.

    In this naive (in terms of both space and time complexity) solution, the vector paths holds a list of pairs, for which the first of the pair is the number of steps to reach current state, and the second of the pair is the current index in the ring. We process each character of key one by one, and for each one of them, we find every possible move (duplicate of this character) in the ring, and expand our vector of paths by calculating the current "circular distance", which we add to each one of the existing paths of the previous step, to find our paths for this step. Finally, we iterate through all paths and find the one with minimum steps.

    This solution is terribly naive and should not be taken seriously. It is only for illustrating the natural thought after first encountering the problem.

    C++

    class Solution {
    public:
        int findRotateSteps(string ring, string key) {
            int r = ring.size(), k = key.size();
            vector<pair<int, int>> paths(1, make_pair(0, 0));
            for (int i = 0; i < k; ++i) {
                vector<pair<int, int>> currentPaths;
                for (int j = 0; j < r; ++j)
                    if (key[i] == ring[j])
                        for (auto path : paths)
                            currentPaths.push_back(make_pair(path.first + circularDistance(r, path.second, j), j));
                paths = currentPaths;
            }
            int minSteps = INT_MAX;
            for (auto path : paths)
                if (path.first < minSteps)
                    minSteps = path.first;
            return minSteps + k;
        }
        int circularDistance(int n, int i, int j) {
            int d = abs(j - i);
            return d > n / 2 ? n - d : d;
        }
    };
    

    Complexity Analysis

    • Time complexity: $$O(kr^k)$$.

    Every character of key (length $$k$$) is process one by one, and for each of them, we iterate through ring (length $$r$$) and find all possible moves for current step, and for each step, we iterate through the previous steps to find all the current steps. The number of steps is bound by $$O(r^k)$$.

    Thus the time complexity is: $$O(kr^k)$$.

    • Space complexity: $$O(r^k)$$.

    Here paths is bounded by $$r^k$$.


    Approach #2 Recursion with Memoization

    Intuition

    Use depth first search to explore the solution space of possible paths: choose the path with optimal step number at every step, instead of choosing the optimal path out of all steps at last.

    Algorithm

    The definition of r and k and the helper function circularDistance are the same as in last approach.

    We employ recursion to process each character of key, and choose the current move out of moves available at this step top-down. The variable ringIdx represents the index in ring of current step, and keyIdx is the index in key that is being processed at this step. c is a minor optimization structure that keeps track of the indices of all duplicates of a character in ring.

    C++

    class Solution {
    private:
        unordered_map<char, vector<int>> c;
    public:
        int findRotateSteps(string ring, string key) {
            for (int i = 0; i < ring.size(); ++i)
                c[ring[i]].push_back(i);
            return rotate(ring, key, 0, 0);
        }
    
        int rotate(string ring, string key, int ringIdx, int keyIdx) {
            if (keyIdx >= key.size())
                return 0;
            int distance = INT_MAX;
            for (int possibleIdx : c[key[keyIdx]]) {
                distance = min(distance, 1 + circularDistance(ring.size(), ringIdx, possibleIdx) + rotate(ring, key, possibleIdx, keyIdx + 1));
            }
            return distance;
        }
    
        int circularDistance(int n, int i, int j) {
            int d = abs(j - i);
            return d > n / 2 ? n - d : d;
        }
    };
    

    Note that the above solution will still result in "Time Limit Exceeded" because it has overlapping sub-problems. A memoization could be easily added to reduce the time complexity: ringIdx and keyIdx combined could encode a unique state of the exploration in the solution space, so they can be used as the key value of memoization structure, which is simply a 2-D matrix of r by k.

    class Solution {
    private:
        unordered_map<char, vector<int>> c;
        vector<vector<int>> mem;
    public:
        int findRotateSteps(string ring, string key) {
            for (int i = 0; i < ring.size(); ++i)
                c[ring[i]].push_back(i);
            mem = vector<vector<int>>(ring.size(), vector<int>(key.size(), 0));
            return rotate(ring, key, 0, 0);
        }
    
        int rotate(string ring, string key, int ringIdx, int keyIdx) {
            if (keyIdx >= key.size())
                return 0;
            if (mem[ringIdx][keyIdx])
                return mem[ringIdx][keyIdx];
            int distance = INT_MAX;
            for (int possibleIdx : c[key[keyIdx]]) {
                distance = min(distance, 1 + circularDistance(ring.size(), ringIdx, possibleIdx) + rotate(ring, key, possibleIdx, keyIdx + 1));
            }
            mem[ringIdx][keyIdx] = distance;
            return distance;
        }
    
        int circularDistance(int n, int i, int j) {
            int d = abs(j - i);
            return d > n / 2 ? n - d : d;
        }
    };
    

    Complexity Analysis

    • Time complexity: $$O(r^k)$$, without memoization; $$O(r^2k)$$, with memoization.

    From the recurrence we know the following equations to be true, where $$k$$ stands for length of key:

    $$T(k) = rT(k - 1)$$

    $$rT(k - 1) = r^2T(k - 2)$$

    ...

    $$r^{k - 1}T(1) = r^kT(0)$$

    Adding them all yields: $$T(k) = r^kT(0)$$.

    Hence the time complexity is: $$O(r^k)$$.

    See next approach for time complexity analysis for the memoized version.

    • Space complexity: $$O(1)$$, without memoization; $$O(rk)$$, with memoization.

    Approach #3 Dynamic Programming Bottom-Up

    Intuition

    Process key one by one, bottom-up. At each step, calculate and store the current optimal paths for re-use in next step.

    Algorithm

    The idea is basically the same as last approach with memoization, but implemented using the bottom-up approach, saving much of the recursion overhead.

    The algorithm logic should be self-evident from reading the code and variable names. A catch is that the memoization structure must be initialized with INT_MAX, except dp[0], which should be filled with zeros. Here prevStep and currStep are indices in ring, and dp[i][currStep] represents the optimal step number after processing key[i - 1], with the current move stepped on ring[currStep]. At last, we find the optimal path in dp[k] with STL's quick select function.

    C++

    class Solution {
    private:
        unordered_map<char, vector<int>> c;
    public:
        int findRotateSteps(string ring, string key) {
            int r = ring.size(), k = key.size();
            for (int i = 0; i < r; ++i)
                c[ring[i]].push_back(i);
            vector<vector<int>> dp(k + 1, vector<int>(r, INT_MAX));
            vector<int> prevSteps(1, 0);
            fill(dp[0].begin(),dp[0].end(),0);
            for (int i = 1; i <= k; ++i) {
                for (int prevStep : prevSteps)
                    for (int currStep : c[key[i - 1]])
                        dp[i][currStep] = min(dp[i][currStep], circularDistance(r, prevStep, currStep) + dp[i - 1][prevStep]);
                prevSteps = c[key[i - 1]];
            }
            nth_element(dp[k].begin(), dp[k].begin(), dp[k].end());
            return dp[k][0] + k;
        }
        
        int circularDistance(int n, int i, int j) {
            int d = abs(j - i);
            return d > n / 2 ? n - d : d;
        }
    };
    

    Complexity Analysis

    • Time complexity: $$O(r^2k)$$.

    The algorithm only consists of a three nested loops. The outer loop has k iterations, and the middle and inner one have prevSteps and currSteps iterations which are both bounded by r. The last quick select is $$O(r)$$. Hence the time complexicity: $$O(r^2k)$$.

    • Space complexity: $$O(rk)$$.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.