核心内容摘要
秦先生短发气质短发合集
2977: 转换字符串的最小成本Ⅱ思路动态规划 图最短路径不相交性质转换操作的子串要么完全相同要么不相交。
这意味着每个位置只需考虑直接转换到最终状态无需考虑中间转换步骤。
子串独立性可以将问题分解为将source的前i个字符变为target的前i个字符的最小代价。
class Solution { public: long long minimumCost(string source, string target, vectorstring original, vectorstring changed, vectorint cost) { int nsource.size(); setint lens; for(const auto str:original) lens.insert(static_castint(str.size())); unordered_setstring orig(original.begin(),original.end()); unordered_setstring chan(changed.begin(),changed.end()); //初始化dp vectorlong long dp(n1,LONG_LONG_MAX); dp[0]0; //构建图 unordered_mapstring,vectorpairstring,int graph; for(int i0;ioriginal.size();i){ graph[original[i]].emplace_back(changed[i],cost[i]); } //dijkstra单源最短路径 auto dijkstra[graph, changed](string src){ unordered_setstring visited; unordered_mapstring,long long dist; for(const auto dest:changed){ dist[dest]LONG_LONG_MAX; } dist[src]0; for(int i0;ichanged.size();i){ auto min_distLONG_LONG_MAX; string min_dest; for(const auto [dest,dist]:dist){ if(!visited.contains(dest) distmin_dist){ min_distdist; min_destdest; } } if(min_distLONG_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_distweightdist[neighbour]){ dist[neighbour]min_distweight; } } } return dist; }; unordered_mapstring,unordered_mapstring,long long dist; for(int i1;in;i){ int j0; while(j*lens.rbegin() i-j-10 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 beginlens.upper_bound(j);begin!lens.end() *begini;begin){ auto len*begin; auto srcsource.substr(i-len,len); auto desttarget.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]; } };