2977. Minimum Cost to Convert String II
解題說明
Minimum Cost to Convert String II
題目描述：給定兩個等長字串 source 和 target，以及三個陣列 original、changed（字串陣列）、cost，表示可以花費 cost[i] 將子字串 original[i] 替換為等長的 changed[i]。求將 source 轉換為 target 的最小總花費，若不可能則回傳 -1。
解題思路：將所有 original 和 changed 字串插入 Trie 並分配唯一編號，相同字串映射到同一節點。以這些節點為圖的頂點，利用 Dijkstra 求出所有對之間的最短轉換成本。接著用 DP：dp[i] 表示轉換 source[i..] 到 target[i..] 的最小成本。對每個位置 i，若 source[i] == target[i] 則可 dp[i] = dp[i+1]；另外在 Trie 中同時走 source[i..] 和 target[i..]，找到匹配的子字串對 (u, v)，嘗試 dp[i] = dp[i+len] + dist[u][v]。
C++ 解法
複雜度分析
時間複雜度：O(V² log V + n × L) — V 為不同字串數量，Dijkstra 全源最短路為 O(V(V + E) log V)；DP 遍歷字串每個位置，每個位置最多走 L 步（L 為最長 original 字串長度）。
空間複雜度：O(V² + T + n) — 距離矩陣 O(V²)，Trie 大小 O(T)，DP 陣列 O(n)。
虛擬碼
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
其他解法
Floyd-Warshall + DP O(V³ + n × L)：用 Floyd-Warshall 取代多源 Dijkstra 求全對最短路。V 可能較大（不像 Part I 固定 26），Dijkstra 在稀疏圖上通常更優。
字串雜湊 + DP O(n × L × V)：不建 Trie，改用雜湊映射每個子字串到其 ID，再做類似 DP。實作簡單但需處理雜湊碰撞問題。
延伸思考
- 如果每個轉換規則只能使用一次（而非無限次），問題變成什麼模型？
- 如果
source和target長度可達 10⁶，如何優化 DP 的內層迴圈？ - 能否用 A* 搜尋取代 Dijkstra 來加速特定情境？