leetcode 2977(Dijkstra + DP)

2977: 转换字符串的最小成本Ⅱ

思路：动态规划 + 图最短路径

• 不相交性质：转换操作的子串要么完全相同，要么不相交。这意味着每个位置只需考虑直接转换到最终状态，无需考虑中间转换步骤。

• 子串独立性：可以将问题分解为：将source的前i个字符变为target的前i个字符的最小代价。

class Solution { public: long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) { int n=source.size(); set<int> lens; for(const auto& str:original) lens.insert(static_cast<int>(str.size())); unordered_set<string> orig(original.begin(),original.end()); unordered_set<string> chan(changed.begin(),changed.end()); //初始化dp vector<long long> dp(n+1,LONG_LONG_MAX); dp[0]=0; //构建图 unordered_map<string,vector<pair<string,int>>> graph; for(int i=0;i<original.size();i++){ graph[original[i]].emplace_back(changed[i],cost[i]); } //dijkstra单源最短路径 auto dijkstra=[&graph, &changed](string& src){ unordered_set<string> visited; unordered_map<string,long long> dist; for(const auto& dest:changed){ dist[dest]=LONG_LONG_MAX; } dist[src]=0; for(int i=0;i<changed.size();i++){ auto min_dist=LONG_LONG_MAX; string min_dest; for(const auto& [dest,dist]:dist){ if(!visited.contains(dest) && dist<min_dist){ min_dist=dist; min_dest=dest; } } if(min_dist==LONG_LONG_MAX) return dist; visited.insert(min_dest); dist[min_dest]=min_dist; for(const auto& [neighbour,weight]:graph[min_dest]){ if(!visited.contains(neighbour) && min_dist+weight<dist[neighbour]){ dist[neighbour]=min_dist+weight; } } } return dist; }; unordered_map<string,unordered_map<string,long long>> dist; for(int i=1;i<=n;i++){ int j=0; while(j<*lens.rbegin() && i-j-1>=0 && source[i-j-1]==target[i-j-1]){ dp[i]=min(dp[i],dp[i-j-1]); j++; } if(j==*lens.rbegin()) continue; //逐个尝试替换不同长度的子串 for(auto begin=lens.upper_bound(j);begin!=lens.end() && *begin<=i;begin++){ auto len=*begin; auto src=source.substr(i-len,len); auto dest=target.substr(i-len,len); if(src!=dest && orig.contains(src) && chan.contains(dest) && dp[i-len]!=LONG_LONG_MAX){ if(!dist.contains(src)) dist[src]=dijkstra(src); if(dist[src][dest]!=LONG_LONG_MAX){ dp[i]=min(dp[i],dp[i-len]+dist[src][dest]); } } } } return dp[n]==LONG_LONG_MAX ? -1:dp[n]; } };