c++ greedy&dp solution 12ms


  • 0
    T
    class Solution {
    public:
        int findRotateSteps(string ring, string key) {
            vector<pair<int,int>> v[26];
            int l = ring.size();
            //init first key char and dp 
            for(int i=0; i<l;i++){
                if(ring[i]==key[0])
                    v[ring[i]-'a'].push_back({i,min(i,l-i)});
                else
                    v[ring[i]-'a'].push_back({i,0});
            }
            //for each key[i], find the min distance for each key[i] in ring 
            for(int i= 1; i< key.size();i++){
                if(key[i]==key[i-1]) continue;
                int cur_c = key[i]-'a';
                int pre_c = key[i-1]-'a';
                for(int j=0;j<v[cur_c].size(); j++){
                    int dis = abs(v[cur_c][j].first - v[pre_c][0].first);
                    v[cur_c][j].second = v[pre_c][0].second + min(dis,l-dis);
                    for(int k=1; k<v[pre_c].size();k++){
                        dis = abs(v[cur_c][j].first - v[pre_c][k].first);
                        v[cur_c][j].second = min(v[cur_c][j].second, v[pre_c][k].second + min(dis,l-dis));  
                    }
                }
            }
            
            //minmum of last
            int idx = key.back()-'a';
            int min_dis=v[idx][0].second;
            for(int i=1; i<v[idx].size();i++){
                min_dis = min(min_dis, v[idx][i].second);
            }
            return min_dis+key.size();
            
        }
    };
    

  • 0
    T
    This post is deleted!

Log in to reply
 

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