Shared my C++ dp solution ,19ms


  • 10

    Simple dp idea

    1. recording each index of characters in ring,beacuse each characters we have search in this time would be starting index in the next search
    2. How could we solve the problem that rotate the ring to the left or right ? My idea is min((tmp[j] + size -it)%size,(it + size - tmp[j])%size)
    • Suppose you want to rotate the ring to the right and search 'k', and the size is 5.
      We could calculate it by this + size -k(index)%size
    this -  -  -  -  k
    
    • If we want to rotate the ring to the left,what should we do? It is the same problem with above problem,move this to its right,and reach k
    k -  -  -  -   this
    
    • So we could calculate it by k(index) + size -this%size
    • There are many people use abs() instead of %size,I think it's faster than mine :)
    class Solution {
    public:
        int findRotateSteps(string ring, string key) {
            int size = ring.size();
            int ksize = key.size();
            unordered_map<char,vector<int>> mp;//stored index of each characters in ring,pay attention to duplcate characters.
            for(int i=0;i<size;++i){
                mp[ring[i]].push_back(i);
            }
            
            vector<vector<int>> dp(ksize+1,vector<int> (size,INT_MAX));// initializing dp vector 
            fill(dp[0].begin(),dp[0].end(),0);
            
            vector<int> tmp(1,0);// starting index
            
            int res = INT_MAX;
            for(int i=1;i<=ksize;++i){
                for(auto it:mp[key[i-1]]){  //
                    for(int j=0;j<tmp.size();++j){  //Search The shortest distance key[i-1] in ring
                        int minDist = min((tmp[j] + size -it)%size,(it + size - tmp[j])%size) + dp[i-1][tmp[j]];// Look at the above explanation
                        dp[i][it] =min(dp[i][it],minDist);
                        res = (i!=ksize?res:min(res,dp[i][it])); //Can we optimize it?
                    }
                }
                tmp = mp[key[i-1]]; //next start is the characters we search in this time
            }
            return res + ksize;
        }
    };
    

    update (optimazed space complexity)

    class Solution {
    public:
        int findRotateSteps(string ring, string key) {
            int size = ring.size();
            int ksize = key.size();
            vector<vector<int>> mp(26);   //Optimazed_1 use vector instead of unordered_map
                //stored index of each ,pay attention to duplcate characters.
            for(int i=0;i<size;++i){
                mp[ring[i]-'a'].push_back(i);
            }
            
            vector<int> dp (size,INT_MAX);   //Optimazed_2,use less space 
            dp[0] = 0;
            
            vector<int> startIndex(1,0);// starting index
    
            for(int i=1;i<=ksize;++i){
                vector<int> nextDp(size,INT_MAX);
                for(auto it:mp[key[i-1]-'a']){
                    for(int j=0;j<startIndex.size();++j){
                        int minDist = min((startIndex[j] + size -it)%size,(it + size - startIndex[j])%size) + dp[startIndex[j]];// Look at the above explanation
                        nextDp[it] =min(nextDp[it],minDist);
                    }
                }
                startIndex = mp[key[i-1]-'a'];
                dp = nextDp;
            }
            
            int res = INT_MAX;
            for(int i=0;i<size;++i){
                res = min(res,dp[i]);
            }  // get the smallest value(step)
            
            return res + ksize;
        }
    };
    
    

  • 0
    S

    clear and easy understanding solution!


  • 0

    Can you explain why the startIndex is initialized as [1, 0] ?


  • 0

    @0x0101
    Firstly , startIndex = [0] not [1,0]
    There is the vector constructor

    vector (size_type n, const value_type& val,const allocator_type& alloc = allocator_type());
    (just understand this )
    vector (size_type n, const value_type& val...);
    

    So vector<int> (1,0) just 1 elements(0) in the container = {0};

    Secondly,We begin at the first elements in rings , it mean we start searching from index 0


Log in to reply
 

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