2977. Minimum Cost to Convert String II

解題說明

C++ 解法

複雜度分析

虛擬碼

1. Build Trie from all original[] and changed[] strings, assign unique ID to each distinct string
2. Build adjacency list: edge from original[i]'s ID to changed[i]'s ID with weight cost[i]
3. Run Dijkstra from each node to compute all-pairs shortest paths dist[u][v]
4. DP from right to left: dp[n] = 0
5. For i = n-1 down to 0:
   a. If source[i] == target[i], dp[i] = dp[i+1]
   b. Walk Trie simultaneously with source[i..] and target[i..]
   c. When both reach word nodes u, v: dp[i] = min(dp[i], dp[i+len] + dist[u][v])
6. Return dp[0] or -1 if INF

其他解法

延伸思考