2977. Minimum Cost to Convert String II

HardGraphTrieArrayStringDynamic ProgrammingShortest Path

Problem Description

You are given two strings source and target of equal length n, consisting of lowercase English letters. You need to transform source into target using a set of allowed string transformations.

The allowed transformations are defined by three arrays:

original[i]: a substring that can be replaced
changed[i]: what original[i] can be changed to
cost[i]: the cost of changing original[i] to changed[i]

Transformation Rules:

In one operation, you can pick any substring x from the current string and change it to y at cost z, provided there exists an index j where original[j] == x, changed[j] == y, and cost[j] == z.
You can perform multiple operations, but they must follow these constraints:
- The substrings selected in different operations must either be disjoint (non-overlapping), meaning if you pick source[a..b] and source[c..d], then either b < c or d < a.
- OR the substrings must be identical (exact same indices), meaning if you pick source[a..b] and source[c..d], then a == c and b == d.

Goal: Find the minimum cost to convert source to target. If it's impossible, return -1.

Important Notes:

Multiple transformation rules can have the same original[i] and changed[i] pairs with different costs.
A substring can be transformed multiple times if the operations use the exact same indices.
The transformations can involve substrings of any length, not just single characters.

Example: If source = "abcd", target = "acbe", and you have transformations that can change "b" to "b" at cost 100, "bc" to "cb" at cost 50, and "d" to "e" at cost 1, you could:

Transform "bc" (at indices 1-2) to "cb" with cost 50
Transform "d" (at index 3) to "e" with cost 1
Total cost: 51

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that this is a dynamic programming problem where we need to find the minimum cost to transform substrings of source into corresponding substrings of target.

First, let's think about what makes this problem complex:

We can transform substrings of any length, not just single characters
The same substring transformation might have multiple costs (we want the minimum)
Transformations can be chained - we might transform "a" to "b" and then "b" to "c"

To handle substring transformations efficiently, we can use a Trie data structure. The Trie allows us to:

Store all possible transformation strings (original and changed)
Assign a unique integer ID to each distinct string
Quickly check if a substring exists in our transformation rules while traversing the source string

Next, we need to handle transitive transformations. If we can transform string A to B with cost X, and B to C with cost Y, then we can transform A to C with cost X+Y. This is a shortest path problem between all pairs of strings. We can model this as a graph where:

Each unique string in original and changed is a node
Each transformation rule is a directed edge with its cost as weight
We use Floyd-Warshall algorithm to find the minimum cost between any two strings

Finally, we need to decide how to apply transformations to convert source to target. We can use memoized recursion with the following approach:

At each position i in the string, we have choices:
- If source[i] == target[i], we can skip this position without any cost
- We can try to transform a substring starting at position i
For each possible substring source[i..j]:
- Check if both source[i..j] and target[i..j] exist in our Trie
- If they do, the cost is g[id_source][id_target] (from Floyd-Warshall) plus the cost of transforming the rest of the string dfs(j+1)
We take the minimum among all valid choices

The memoization ensures we don't recalculate the same subproblems, making the solution efficient.

Learn more about Graph, Trie, Dynamic Programming and Shortest Path patterns.

Solution Approach

The solution consists of three main components: building a Trie for string mapping, computing shortest paths using Floyd-Warshall, and finding the minimum cost using memoized recursion.

1. Building the Trie and String Mapping

We create a Trie to store all unique strings from original and changed arrays. Each string gets a unique integer identifier:

class Node:
    def __init__(self):
        self.children = [None] * 26  # For lowercase letters a-z
        self.v = -1  # String ID, -1 means no string ends here

def insert(w: str) -> int:
    node = root
    for c in w:
        i = ord(c) - ord("a")
        if node.children[i] is None:
            node.children[i] = Node()
        node = node.children[i]
    if node.v < 0:
        node.v = idx
        idx += 1
    return node.v

2. Building the Cost Graph

We initialize a 2D array g where g[i][j] represents the minimum cost to transform string with ID i to string with ID j:

m = len(cost)
g = [[inf] * (m << 1) for _ in range(m << 1)]  # Size is 2*m to accommodate all possible strings
for i in range(m << 1):
    g[i][i] = 0  # Cost to transform a string to itself is 0

# Add direct transformation costs
for x, y, z in zip(original, changed, cost):
    x_id = insert(x)  # Get/assign ID for original string
    y_id = insert(y)  # Get/assign ID for changed string
    g[x_id][y_id] = min(g[x_id][y_id], z)  # Take minimum if duplicate rules exist

3. Floyd-Warshall Algorithm

We compute the shortest path between all pairs of strings to handle transitive transformations:

for k in range(idx):  # idx is the total number of unique strings
    for i in range(idx):
        if g[i][k] >= inf:
            continue  # Optimization: skip if no path from i to k
        for j in range(idx):
            if g[i][k] + g[k][j] < g[i][j]:
                g[i][j] = g[i][k] + g[k][j]

4. Memoized Recursion

The core dynamic programming function dfs(i) computes the minimum cost to transform source[i:] to target[i:]:

@cache
def dfs(i: int) -> int:
    if i >= len(source):
        return 0  # Base case: reached end of string
  
    # Option 1: Skip if characters match
    res = dfs(i + 1) if source[i] == target[i] else inf
  
    # Option 2: Try transforming substrings starting at position i
    p = q = root  # Traverse both source and target in the [Trie](/problems/trie_intro)
    for j in range(i, len(source)):
        p = p.children[ord(source[j]) - ord("a")]
        q = q.children[ord(target[j]) - ord("a")]
      
        if p is None or q is None:
            break  # Substring doesn't exist in Trie
      
        if p.v >= 0 and q.v >= 0:  # Both substrings have valid IDs
            # Cost = transform source[i:j+1] to target[i:j+1] + solve rest
            res = min(res, dfs(j + 1) + g[p.v][q.v])
  
    return res

5. Final Result

ans = dfs(0)
return -1 if ans >= inf else ans

The algorithm returns -1 if transformation is impossible (cost remains inf), otherwise returns the minimum cost.

Time Complexity:

Building Trie: O(L) where L is total length of all strings
Floyd-Warshall: O(n³) where n is number of unique strings
DFS with memoization: O(|source|²) states with O(|source|) work per state

Space Complexity: O(n² + |source|) for the graph and memoization cache

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

source = "abc"
target = "aec"
original = ["b", "bc"]
changed = ["e", "ec"]
cost = [2, 5]

Step 1: Build Trie and Assign IDs

We insert all strings from original and changed into the Trie:

Insert "b" → gets ID 0
Insert "e" → gets ID 1
Insert "bc" → gets ID 2
Insert "ec" → gets ID 3

Our Trie structure:

root
├── b (ID: 0)
│   └── c (ID: 2)
└── e (ID: 1)
    └── c (ID: 3)

Step 2: Build Initial Cost Graph

Initialize graph g with infinity, except diagonal (0s):

g[0][1] = 2  // "b" → "e" costs 2
g[2][3] = 5  // "bc" → "ec" costs 5

Step 3: Floyd-Warshall (No Changes)

Since there are no intermediate transformations possible, the graph remains unchanged.

Step 4: Memoized Recursion - dfs(0)

Starting at position 0:

source[0] = 'a', target[0] = 'a' → they match!
Option 1: Skip position 0, compute dfs(1)

Computing dfs(1):

At position 1:

source[1] = 'b', target[1] = 'e' → they don't match
Option 1: Skip (returns inf since characters don't match)
Option 2: Try transformations starting at position 1:

Substring length 1: source[1:2] = "b", target[1:2] = "e"
- Both exist in Trie with IDs 0 and 1
- Cost = g[0][1] + dfs(2) = 2 + dfs(2)
Substring length 2: source[1:3] = "bc", target[1:3] = "ec"
- Both exist in Trie with IDs 2 and 3
- Cost = g[2][3] + dfs(3) = 5 + dfs(3)

Computing dfs(2):

At position 2:

source[2] = 'c', target[2] = 'c' → they match!
Option 1: Skip position 2, compute dfs(3) = 0 (base case)
Result: dfs(2) = 0

Computing dfs(3):

Base case: position 3 >= length(3)
Result: dfs(3) = 0

Backtracking:

dfs(1) = min(inf, 2 + 0, 5 + 0) = min(inf, 2, 5) = 2
dfs(0) = 0 + 2 = 2

Final Answer: 2

The optimal transformation:

Keep 'a' at position 0 (no cost)
Transform "b" at position 1 to "e" (cost 2)
Keep 'c' at position 2 (no cost)

Total cost: 2

Solution Implementation

1from typing import List
2from functools import cache
3from math import inf
4
5
6class TrieNode:
7    """Trie node for storing string patterns"""
8    __slots__ = ["children", "word_id"]
9  
10    def __init__(self):
11        # Array of 26 children nodes (one for each lowercase letter)
12        self.children: List[TrieNode | None] = [None] * 26
13        # ID assigned to complete words ending at this node (-1 if not a word ending)
14        self.word_id = -1
15
16
17class Solution:
18    def minimumCost(
19        self,
20        source: str,
21        target: str,
22        original: List[str],
23        changed: List[str],
24        cost: List[int],
25    ) -> int:
26        """
27        Find minimum cost to transform source string to target string using given transformations.
28      
29        Args:
30            source: Source string to transform
31            target: Target string to achieve
32            original: List of original substrings that can be replaced
33            changed: List of replacement substrings
34            cost: List of costs for each transformation
35          
36        Returns:
37            Minimum cost to transform source to target, or -1 if impossible
38        """
39        num_transformations = len(cost)
40        # Initialize adjacency matrix for shortest path calculation
41        # Size is doubled to accommodate all possible unique strings
42        max_nodes = num_transformations << 1  # num_transformations * 2
43        graph = [[inf] * max_nodes for _ in range(max_nodes)]
44      
45        # Distance from any node to itself is 0
46        for i in range(max_nodes):
47            graph[i][i] = 0
48      
49        # Initialize trie root and word counter
50        trie_root = TrieNode()
51        word_counter = 0
52      
53        def insert_word(word: str) -> int:
54            """
55            Insert a word into the trie and return its unique ID.
56          
57            Args:
58                word: String to insert into trie
59              
60            Returns:
61                Unique ID assigned to this word
62            """
63            nonlocal word_counter
64            current_node = trie_root
65          
66            # Traverse/build trie path for the word
67            for char in word:
68                char_index = ord(char) - ord('a')
69                if current_node.children[char_index] is None:
70                    current_node.children[char_index] = TrieNode()
71                current_node = current_node.children[char_index]
72          
73            # Assign unique ID if this word hasn't been seen before
74            if current_node.word_id < 0:
75                current_node.word_id = word_counter
76                word_counter += 1
77              
78            return current_node.word_id
79      
80        @cache
81        def find_min_cost(position: int) -> int:
82            """
83            Find minimum cost to transform source[position:] to target[position:].
84            Uses dynamic programming with memoization.
85          
86            Args:
87                position: Current position in the source/target strings
88              
89            Returns:
90                Minimum cost to complete transformation from this position
91            """
92            # Base case: reached end of strings
93            if position >= len(source):
94                return 0
95          
96            # Option 1: Skip current position if characters already match
97            result = find_min_cost(position + 1) if source[position] == target[position] else inf
98          
99            # Option 2: Try all possible substring replacements starting at current position
100            source_node = trie_root
101            target_node = trie_root
102          
103            for end_pos in range(position, len(source)):
104                # Navigate both tries simultaneously
105                source_char_index = ord(source[end_pos]) - ord('a')
106                target_char_index = ord(target[end_pos]) - ord('a')
107              
108                source_node = source_node.children[source_char_index]
109                target_node = target_node.children[target_char_index]
110              
111                # Stop if either path doesn't exist in trie
112                if source_node is None or target_node is None:
113                    break
114              
115                # Skip if either substring is not a complete word in our dictionary
116                if source_node.word_id < 0 or target_node.word_id < 0:
117                    continue
118              
119                # Try this transformation and recursively solve the rest
120                transformation_cost = graph[source_node.word_id][target_node.word_id]
121                result = min(result, find_min_cost(end_pos + 1) + transformation_cost)
122          
123            return result
124      
125        # Build graph of transformation costs
126        for orig_str, changed_str, trans_cost in zip(original, changed, cost):
127            orig_id = insert_word(orig_str)
128            changed_id = insert_word(changed_str)
129            # Keep minimum cost if multiple transformations exist
130            graph[orig_id][changed_id] = min(graph[orig_id][changed_id], trans_cost)
131      
132        # Floyd-Warshall algorithm to find shortest paths between all word pairs
133        for k in range(word_counter):
134            for i in range(word_counter):
135                # Skip if no path through k from i
136                if graph[i][k] >= inf:
137                    continue
138                for j in range(word_counter):
139                    # Update shortest path from i to j through k
140                    if graph[i][k] + graph[k][j] < graph[i][j]:
141                        graph[i][j] = graph[i][k] + graph[k][j]
142      
143        # Find minimum cost starting from position 0
144        min_cost = find_min_cost(0)
145      
146        # Return -1 if transformation is impossible, otherwise return the cost
147        return -1 if min_cost >= inf else min_cost
148

1class Node {
2    Node[] children = new Node[26];  // Array to store child nodes for each letter (a-z)
3    int nodeId = -1;  // ID assigned to this node if it represents end of a string
4}
5
6class Solution {
7    private static final long INFINITY = 1L << 60;  // Large value representing infinity
8    private Node trieRoot = new Node();  // Root of the Trie data structure
9    private int nodeIdCounter;  // Counter for assigning unique IDs to trie nodes
10  
11    private long[][] costMatrix;  // Floyd-Warshall shortest path matrix
12    private char[] sourceChars;  // Source string as character array
13    private char[] targetChars;  // Target string as character array
14    private Long[] memoization;  // DP memoization array for minimum cost
15  
16    public long minimumCost(
17        String source, String target, String[] original, String[] changed, int[] cost) {
18        int numTransformations = cost.length;
19      
20        // Initialize cost matrix with maximum possible nodes (2 * number of transformations)
21        costMatrix = new long[numTransformations << 1][numTransformations << 1];
22        sourceChars = source.toCharArray();
23        targetChars = target.toCharArray();
24      
25        // Initialize cost matrix with infinity, except diagonal (cost to self = 0)
26        for (int i = 0; i < costMatrix.length; ++i) {
27            Arrays.fill(costMatrix[i], INFINITY);
28            costMatrix[i][i] = 0;
29        }
30      
31        // Build trie and populate initial costs for direct transformations
32        for (int i = 0; i < numTransformations; ++i) {
33            int fromNodeId = insertIntoTrie(original[i]);
34            int toNodeId = insertIntoTrie(changed[i]);
35            // Keep minimum cost if multiple transformations exist
36            costMatrix[fromNodeId][toNodeId] = Math.min(costMatrix[fromNodeId][toNodeId], cost[i]);
37        }
38      
39        // Floyd-Warshall algorithm to find shortest paths between all pairs
40        for (int intermediate = 0; intermediate < nodeIdCounter; ++intermediate) {
41            for (int from = 0; from < nodeIdCounter; ++from) {
42                // Skip if no path through intermediate node
43                if (costMatrix[from][intermediate] >= INFINITY) {
44                    continue;
45                }
46                for (int to = 0; to < nodeIdCounter; ++to) {
47                    costMatrix[from][to] = Math.min(
48                        costMatrix[from][to], 
49                        costMatrix[from][intermediate] + costMatrix[intermediate][to]
50                    );
51                }
52            }
53        }
54      
55        // Initialize memoization array and compute result using DFS
56        memoization = new Long[sourceChars.length];
57        long result = computeMinimumCost(0);
58        return result >= INFINITY ? -1 : result;
59    }
60  
61    /**
62     * Inserts a word into the trie and returns its node ID
63     */
64    private int insertIntoTrie(String word) {
65        Node currentNode = trieRoot;
66      
67        // Traverse/create path in trie for the word
68        for (char character : word.toCharArray()) {
69            int index = character - 'a';
70            if (currentNode.children[index] == null) {
71                currentNode.children[index] = new Node();
72            }
73            currentNode = currentNode.children[index];
74        }
75      
76        // Assign unique ID to the end node if not already assigned
77        if (currentNode.nodeId < 0) {
78            currentNode.nodeId = nodeIdCounter++;
79        }
80        return currentNode.nodeId;
81    }
82  
83    /**
84     * DFS with memoization to find minimum cost to transform source to target
85     * starting from position i
86     */
87    private long computeMinimumCost(int position) {
88        // Base case: reached end of string
89        if (position >= sourceChars.length) {
90            return 0;
91        }
92      
93        // Return memoized result if available
94        if (memoization[position] != null) {
95            return memoization[position];
96        }
97      
98        // Option 1: If characters match, skip transformation
99        long minCost = sourceChars[position] == targetChars[position] ? 
100            computeMinimumCost(position + 1) : INFINITY;
101      
102        // Option 2: Try all possible substring transformations starting at position
103        Node sourceNode = trieRoot;
104        Node targetNode = trieRoot;
105      
106        for (int endPos = position; endPos < sourceChars.length; ++endPos) {
107            // Traverse both tries simultaneously
108            sourceNode = sourceNode.children[sourceChars[endPos] - 'a'];
109            targetNode = targetNode.children[targetChars[endPos] - 'a'];
110          
111            // Stop if either path doesn't exist
112            if (sourceNode == null || targetNode == null) {
113                break;
114            }
115          
116            // Skip if not complete words in trie
117            if (sourceNode.nodeId < 0 || targetNode.nodeId < 0) {
118                continue;
119            }
120          
121            // Check if transformation exists and update minimum cost
122            long transformationCost = costMatrix[sourceNode.nodeId][targetNode.nodeId];
123            if (transformationCost < INFINITY) {
124                minCost = Math.min(minCost, transformationCost + computeMinimumCost(endPos + 1));
125            }
126        }
127      
128        // Memoize and return result
129        memoization[position] = minCost;
130        return minCost;
131    }
132}
133

1class TrieNode {
2public:
3    TrieNode* children[26];
4    int nodeIndex = -1;  // Index assigned to this node if it represents a complete string
5  
6    TrieNode() {
7        fill(children, children + 26, nullptr);
8    }
9};
10
11class Solution {
12private:
13    static const long long INF = 1LL << 60;  // Large value representing infinity
14    TrieNode* trieRoot = new TrieNode();
15    int nextNodeIndex = 0;  // Counter for assigning unique indices to trie nodes
16  
17    vector<vector<long long>> costGraph;  // Adjacency matrix for transformation costs
18    string sourceStr;
19    string targetStr;
20    vector<long long> memo;  // Memoization array for dynamic programming
21  
22public:
23    long long minimumCost(string source, string target, vector<string>& original, 
24                         vector<string>& changed, vector<int>& cost) {
25        int numTransformations = cost.size();
26      
27        // Initialize cost graph with infinity (2*m size to accommodate all possible nodes)
28        costGraph = vector<vector<long long>>(numTransformations << 1, 
29                                              vector<long long>(numTransformations << 1, INF));
30        sourceStr = source;
31        targetStr = target;
32      
33        // Set diagonal to 0 (cost of transforming a string to itself)
34        for (int i = 0; i < costGraph.size(); ++i) {
35            costGraph[i][i] = 0;
36        }
37      
38        // Build the cost graph by inserting strings into trie and recording transformation costs
39        for (int i = 0; i < numTransformations; ++i) {
40            int fromIndex = insertIntoTrie(original[i]);
41            int toIndex = insertIntoTrie(changed[i]);
42            // Keep minimum cost if multiple transformations exist
43            costGraph[fromIndex][toIndex] = min(costGraph[fromIndex][toIndex], 
44                                                static_cast<long long>(cost[i]));
45        }
46      
47        // Floyd-Warshall algorithm to find shortest paths between all pairs
48        for (int k = 0; k < nextNodeIndex; ++k) {
49            for (int i = 0; i < nextNodeIndex; ++i) {
50                if (costGraph[i][k] >= INF) {
51                    continue;  // Skip if no path exists
52                }
53                for (int j = 0; j < nextNodeIndex; ++j) {
54                    costGraph[i][j] = min(costGraph[i][j], costGraph[i][k] + costGraph[k][j]);
55                }
56            }
57        }
58      
59        // Initialize memoization array for dynamic programming
60        memo = vector<long long>(sourceStr.length(), -1);
61      
62        // Compute minimum cost using DFS with memoization
63        long long result = computeMinCost(0);
64        return result >= INF ? -1 : result;
65    }
66  
67private:
68    // Insert a string into the trie and return its assigned index
69    int insertIntoTrie(const string& word) {
70        TrieNode* currentNode = trieRoot;
71      
72        // Traverse or create path in trie for the word
73        for (char ch : word) {
74            int charIndex = ch - 'a';
75            if (currentNode->children[charIndex] == nullptr) {
76                currentNode->children[charIndex] = new TrieNode();
77            }
78            currentNode = currentNode->children[charIndex];
79        }
80      
81        // Assign a unique index to this node if it doesn't have one
82        if (currentNode->nodeIndex < 0) {
83            currentNode->nodeIndex = nextNodeIndex++;
84        }
85        return currentNode->nodeIndex;
86    }
87  
88    // DFS with memoization to find minimum cost starting from position i
89    long long computeMinCost(int position) {
90        // Base case: reached end of string
91        if (position >= sourceStr.length()) {
92            return 0;
93        }
94      
95        // Return memoized result if already computed
96        if (memo[position] != -1) {
97            return memo[position];
98        }
99      
100        // Option 1: If characters match, skip transformation
101        long long minCost = (sourceStr[position] == targetStr[position]) ? 
102                            computeMinCost(position + 1) : INF;
103      
104        // Option 2: Try all possible substring transformations starting at position
105        TrieNode* sourceNode = trieRoot;
106        TrieNode* targetNode = trieRoot;
107      
108        for (int endPos = position; endPos < sourceStr.length(); ++endPos) {
109            // Traverse both source and target tries simultaneously
110            sourceNode = sourceNode->children[sourceStr[endPos] - 'a'];
111            targetNode = targetNode->children[targetStr[endPos] - 'a'];
112          
113            // Stop if either path doesn't exist in trie
114            if (sourceNode == nullptr || targetNode == nullptr) {
115                break;
116            }
117          
118            // Skip if current nodes don't represent complete strings
119            if (sourceNode->nodeIndex < 0 || targetNode->nodeIndex < 0) {
120                continue;
121            }
122          
123            // Check if transformation exists and update minimum cost
124            long long transformCost = costGraph[sourceNode->nodeIndex][targetNode->nodeIndex];
125            if (transformCost < INF) {
126                minCost = min(minCost, transformCost + computeMinCost(endPos + 1));
127            }
128        }
129      
130        // Memoize and return result
131        return memo[position] = minCost;
132    }
133};
134

1// Trie node structure for storing string patterns
2interface TrieNode {
3    children: (TrieNode | null)[];  // 26 children for each letter a-z
4    nodeId: number;                  // Unique ID for this node (-1 if not a word ending)
5}
6
7// Create a new trie node
8function createTrieNode(): TrieNode {
9    return {
10        children: Array(26).fill(null),
11        nodeId: -1
12    };
13}
14
15// Global variables
16let trieRoot: TrieNode;
17let nodeIdCounter: number;
18let transformationCostGraph: number[][];
19let memoizationCache: number[];
20let sourceString: string;
21let targetString: string;
22let stringLength: number;
23
24// Insert a word into the trie and return its node ID
25function insertIntoTrie(word: string): number {
26    let currentNode: TrieNode = trieRoot;
27  
28    // Traverse or create path for each character
29    for (const char of word) {
30        const charIndex: number = char.charCodeAt(0) - 'a'.charCodeAt(0);
31      
32        if (currentNode.children[charIndex] === null) {
33            currentNode.children[charIndex] = createTrieNode();
34        }
35      
36        currentNode = currentNode.children[charIndex] as TrieNode;
37    }
38  
39    // Assign a unique ID if this is a new word ending
40    if (currentNode.nodeId < 0) {
41        currentNode.nodeId = nodeIdCounter++;
42    }
43  
44    return currentNode.nodeId;
45}
46
47// Dynamic programming function to find minimum cost starting from position i
48function findMinimumCostFromPosition(position: number): number {
49    // Base case: reached end of string
50    if (position >= stringLength) {
51        return 0;
52    }
53  
54    // Return memoized result if available
55    if (memoizationCache[position] !== -1) {
56        return memoizationCache[position];
57    }
58  
59    // Option 1: Skip current position if source and target characters match
60    let minimumCost: number = sourceString[position] === targetString[position] 
61        ? findMinimumCostFromPosition(position + 1) 
62        : Infinity;
63  
64    // Option 2: Try all possible substring transformations starting from current position
65    let sourceTrieNode: TrieNode = trieRoot;
66    let targetTrieNode: TrieNode = trieRoot;
67  
68    for (let endPosition = position; endPosition < stringLength; ++endPosition) {
69        // Navigate through trie for both source and target substrings
70        const sourceCharIndex = sourceString[endPosition].charCodeAt(0) - 'a'.charCodeAt(0);
71        const targetCharIndex = targetString[endPosition].charCodeAt(0) - 'a'.charCodeAt(0);
72      
73        sourceTrieNode = sourceTrieNode.children[sourceCharIndex] as TrieNode;
74        targetTrieNode = targetTrieNode.children[targetCharIndex] as TrieNode;
75      
76        // Stop if either path doesn't exist in trie
77        if (sourceTrieNode === null || targetTrieNode === null) {
78            break;
79        }
80      
81        // Skip if either substring is not a complete word in our transformation set
82        if (sourceTrieNode.nodeId < 0 || targetTrieNode.nodeId < 0) {
83            continue;
84        }
85      
86        // Calculate cost: transformation cost + cost of remaining string
87        const transformationCost: number = transformationCostGraph[sourceTrieNode.nodeId][targetTrieNode.nodeId];
88        minimumCost = Math.min(minimumCost, transformationCost + findMinimumCostFromPosition(endPosition + 1));
89    }
90  
91    // Memoize and return result
92    memoizationCache[position] = minimumCost;
93    return minimumCost;
94}
95
96function minimumCost(
97    source: string,
98    target: string,
99    original: string[],
100    changed: string[],
101    cost: number[],
102): number {
103    // Initialize global variables
104    const numberOfTransformations = cost.length;
105    stringLength = source.length;
106    sourceString = source;
107    targetString = target;
108  
109    // Initialize transformation cost graph with infinity (no direct path)
110    transformationCostGraph = Array.from(
111        { length: numberOfTransformations << 1 }, 
112        () => Array(numberOfTransformations << 1).fill(Infinity)
113    );
114  
115    // Initialize trie and related variables
116    trieRoot = createTrieNode();
117    nodeIdCounter = 0;
118  
119    // Initialize memoization cache
120    memoizationCache = Array(stringLength).fill(-1);
121  
122    // Build trie and initial cost graph from transformation rules
123    for (let i = 0; i < numberOfTransformations; ++i) {
124        const sourceNodeId: number = insertIntoTrie(original[i]);
125        const targetNodeId: number = insertIntoTrie(changed[i]);
126      
127        // Update cost graph with minimum cost for this transformation
128        transformationCostGraph[sourceNodeId][targetNodeId] = 
129            Math.min(transformationCostGraph[sourceNodeId][targetNodeId], cost[i]);
130    }
131  
132    // Apply Floyd-Warshall algorithm to find shortest paths between all node pairs
133    for (let intermediate = 0; intermediate < nodeIdCounter; ++intermediate) {
134        for (let start = 0; start < nodeIdCounter; ++start) {
135            // Skip if no path through intermediate node
136            if (transformationCostGraph[start][intermediate] >= Infinity) {
137                continue;
138            }
139          
140            for (let end = 0; end < nodeIdCounter; ++end) {
141                // Update shortest path from start to end through intermediate
142                transformationCostGraph[start][end] = Math.min(
143                    transformationCostGraph[start][end],
144                    transformationCostGraph[start][intermediate] + transformationCostGraph[intermediate][end]
145                );
146            }
147        }
148    }
149  
150    // Find minimum cost using dynamic programming
151    const result: number = findMinimumCostFromPosition(0);
152  
153    // Return -1 if transformation is impossible, otherwise return the cost
154    return result >= Infinity ? -1 : result;
155}
156

Time and Space Complexity

Time Complexity: O(m^3 + n^2 + m × n)

The time complexity breaks down into several components:

Building the Trie and inserting strings: Each string in original and changed arrays is inserted into the Trie. With m strings and assuming average/maximum string length is bounded, this takes O(m × L) where L is the maximum length of strings. In the context of this problem, L can be considered as part of n (length of source string), giving us O(m × n).
Floyd-Warshall algorithm: The triple nested loop runs through all idx values where idx ≤ m (since we have at most m unique string nodes). This gives us O(idx^3) = O(m^3).
DFS with memoization: The dfs function can be called with at most n different starting positions. For each call, the inner loop iterates from position i to n, and for each position, it traverses the Trie which takes O(n) in worst case. This gives us O(n^2) for the DFS traversal.

Space Complexity: O(m^2 + m × n + n)

The space complexity consists of:

Graph matrix g: A 2D array of size (m << 1) × (m << 1) which simplifies to O(m^2).
Trie structure: The Trie stores all strings from original and changed. With m strings of maximum length bounded by n, the Trie uses O(m × n) space.
Memoization cache: The @cache decorator on dfs stores results for up to n different starting positions, using O(n) space.
Recursion stack: The maximum recursion depth is n, contributing O(n) to space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Overlapping Transformations

Pitfall: One of the most critical mistakes is misunderstanding the constraint about overlapping transformations. Developers often incorrectly assume that any overlapping transformations are allowed, or conversely, that no overlapping is permitted at all.

The Problem: The rules state that transformations must be either:

Completely disjoint (non-overlapping), OR
Exactly identical (same indices)

This means you CANNOT apply transformations like:

Transform source[0:3] then source[1:4] (partial overlap)
Transform source[0:2] then source[0:3] (one contains the other)

Solution: The recursive approach with memoization naturally handles this by processing the string left-to-right. Once we transform a substring starting at position i and ending at position j, we recursively solve for position j+1, ensuring no improper overlaps occur.

2. Missing Transitive Transformations

Pitfall: Only considering direct transformations from the input arrays and missing that you can chain transformations together.

Example: If you can transform "ab" → "cd" (cost 10) and "cd" → "ef" (cost 5), you should be able to transform "ab" → "ef" with total cost 15, even if this direct transformation isn't in the input.

Solution: Use Floyd-Warshall algorithm to compute the shortest path between all pairs of strings, capturing all possible transformation chains:

for k in range(word_counter):
    for i in range(word_counter):
        if graph[i][k] >= inf:
            continue
        for j in range(word_counter):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

3. Insufficient Graph Size Allocation

Pitfall: Allocating the graph size based only on the length of the original array, forgetting that strings in changed might be unique and not appear in original.

Example Problem:

# WRONG: Only accounts for strings in original
graph = [[inf] * len(original) for _ in range(len(original))]

# This fails when changed contains strings not in original

Solution: Allocate the graph to handle all possible unique strings from both arrays:

max_nodes = len(cost) * 2  # Conservative upper bound
graph = [[inf] * max_nodes for _ in range(max_nodes)]

4. Not Handling Duplicate Transformation Rules

Pitfall: When multiple rules exist for the same transformation (same original[i] and changed[i] pair but different costs), incorrectly overwriting instead of taking the minimum cost.

Example:

# WRONG: Overwrites previous cost
graph[orig_id][changed_id] = trans_cost

# CORRECT: Keeps minimum cost
graph[orig_id][changed_id] = min(graph[orig_id][changed_id], trans_cost)

5. Forgetting to Check Valid Word IDs in Trie

Pitfall: During the DFS traversal, attempting to use transformation costs for substrings that don't exist as complete words in the transformation rules.

Problem Code:

# WRONG: Doesn't verify if substrings are valid transformation endpoints
for j in range(position, len(source)):
    source_node = source_node.children[...]
    target_node = target_node.children[...]
    # Immediately tries to use graph[source_node.word_id][target_node.word_id]

Solution: Always check if both nodes have valid word IDs before attempting transformation:

if source_node.word_id < 0 or target_node.word_id < 0:
    continue  # Skip if not valid transformation endpoints

6. Early Termination in Substring Search

Pitfall: Not properly handling the case where we should continue checking longer substrings even if shorter ones don't have valid transformations.

Solution: Use continue instead of break when word IDs are invalid, only break when the trie path doesn't exist:

if source_node is None or target_node is None:
    break  # No longer substring exists in trie
  
if source_node.word_id < 0 or target_node.word_id < 0:
    continue  # This substring isn't a valid word, but longer ones might be

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know