2977. Minimum Cost to Convert String II

1import java.util.Arrays;
2
3class Node {
4    Node[] children = new Node[26];
5    int valueIndex = -1; // Initialize with -1 to indicate not assigned.
6}
7
8class Solution {
9    private final long INF = 1L << 60; // A large value to represent infinity in the context.
10    private Node root = new Node();    // Trie root node.
11    private int index;                 // Tracks indices for the nodes in the trie.
12
13    private long[][] graph; // Represents the cost graph between trie node indices.
14    private char[] sourceArray; // Source string to character array.
15    private char[] targetArray; // Target string to character array.
16    private Long[] dpMemo;      // Dynamic programming memoization table.
17
18    // Computes the minimum cost to convert the `source` string to the `target` string.
19    public long minimumCost(
20        String source, String target, String[] originals, String[] changeds, int[] costs) {
21        int transformationCount = costs.length;
22        graph = new long[transformationCount << 1][transformationCount << 1];
23        sourceArray = source.toCharArray();
24        targetArray = target.toCharArray();
25
26        // Initialize graph with INF and 0 on the diagonal (no cost to convert to itself).
27        for (int i = 0; i < graph.length; ++i) {
28            Arrays.fill(graph[i], INF);
29            graph[i][i] = 0;
30        }
31
32        // Build the trie and graph with minimum costs between conversions.
33        for (int i = 0; i < transformationCount; ++i) {
34            int startIndex = insertIntoTrie(originals[i]);
35            int endIndex = insertIntoTrie(changeds[i]);
36            graph[startIndex][endIndex] = Math.min(graph[startIndex][endIndex], costs[i]);
37        }
38
39        // Floyd-Warshall algorithm to find all-pairs shortest paths in the graph.
40        for (int k = 0; k < index; ++k) {
41            for (int i = 0; i < index; ++i) {
42                if (graph[i][k] >= INF) {
43                    continue; // Skip if there is no path from i to k.
44                }
45                for (int j = 0; j < index; ++j) {
46                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
47                }
48            }
49        }
50
51        // Initialize dynamic programming memoization table.
52        dpMemo = new Long[sourceArray.length];
53        // Start the recursive depth-first search from index 0.
54        long answer = dfs(0);
55        // If the result is INF, no valid conversion exists; return -1.
56        return answer >= INF ? -1 : answer;
57    }
58
59    // Inserts a string into the trie and returns its index (valueIndex).
60    private int insertIntoTrie(String word) {
61        Node node = root;
62        for (char c : word.toCharArray()) {
63            int index = c - 'a';
64            if (node.children[index] == null) {
65                node.children[index] = new Node();
66            }
67            node = node.children[index];
68        }
69        if (node.valueIndex < 0) {
70            node.valueIndex = index++; // Assign index if not already assigned.
71        }
72        return node.valueIndex;
73    }
74
75    // Recursive depth-first search function to compute minimum cost.
76    private long dfs(int currentIndex) {
77        // Base case: If we've reached the end of the source array, no cost needed.
78        if (currentIndex >= sourceArray.length) {
79            return 0;
80        }
81        // Retrieve precomputed result from memo table if it exists.
82        if (dpMemo[currentIndex] != null) {
83            return dpMemo[currentIndex];
84        }
85        // Compare characters at the current index of source and target strings.
86        long result = sourceArray[currentIndex] == targetArray[currentIndex] ? dfs(currentIndex + 1) : INF;
87
88        // Search for the cheapest conversion from currentIndex to the end of strings.
89        Node sourceNode = root, targetNode = root;
90        for (int j = currentIndex; j < sourceArray.length; ++j) {
91            sourceNode = sourceNode.children[sourceArray[j] - 'a'];
92            targetNode = targetNode.children[targetArray[j] - 'a'];
93            if (sourceNode == null || targetNode == null) {
94                break; // No possible conversion if either nodes are null.
95            }
96            if (sourceNode.valueIndex < 0 || targetNode.valueIndex < 0) {
97                continue; // If no index assigned to nodes, skip.
98            }
99            long transformationCost = graph[sourceNode.valueIndex][targetNode.valueIndex];
100            if (transformationCost < INF) {
101                result = Math.min(result, transformationCost + dfs(j + 1));
102            }
103        }
104        // Store the result in memoization table and return.
105        return dpMemo[currentIndex] = result;
106    }
107}
108

1class Node {
2public:
3    Node* children[26]; // Pointers to child Nodes, one for each letter in the alphabet
4    int value = -1;     // Unique identifier for the node, -1 means uninitialized
5    Node() {
6        fill(begin(children), end(children), nullptr);
7    }
8};
9
10class Solution {
11private:
12    const long long kInf = 1LL << 60; // Represents an unreachable state or infinity
13    Node* root = new Node();           // Root of the trie
14    int index;                         // Index to assign unique IDs to trie nodes
15
16    vector<vector<long long>> graph;   // Representation of the transformation costs as a graph
17    string sourceString;               // Source string to transform from
18    string targetString;               // Target string to transform to
19    vector<long long> memoizationCache; // Memoization cache to store results of subproblems
20
21public:
22    long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
23        int modificationCount = cost.size();
24        graph = vector<vector<long long>>(modificationCount << 1, vector<long long>(modificationCount << 1, kInf));
25        sourceString = source;
26        targetString = target;
27
28        // Set self-transformation cost to 0
29        for (int i = 0; i < graph.size(); ++i) {
30            graph[i][i] = 0;
31        }
32
33        // Build the graph with transformation costs
34        for (int i = 0; i < modificationCount; ++i) {
35            int fromIndex = insert(original[i]);
36            int toIndex = insert(changed[i]);
37            graph[fromIndex][toIndex] = min(graph[fromIndex][toIndex], static_cast<long long>(cost[i]));
38        }
39
40        // Floyd-Warshall algorithm to find all pairs shortest paths
41        for (int k = 0; k < index; ++k) {
42            for (int i = 0; i < index; ++i) {
43                if (graph[i][k] >= kInf) continue; // Skip over infinite costs
44                for (int j = 0; j < index; ++j) {
45                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
46                }
47            }
48        }
49
50        // Initialize memoization cache for DFS
51        memoizationCache = vector<long long>(sourceString.length(), -1);
52        long long answer = depthFirstSearch(0);
53        // Return -1 if it is not possible to transform source to target string within given costs
54        return answer >= kInf ? -1 : answer;
55    }
56
57private:
58    // Inserts a word into the trie and returns its index
59    int insert(const string& word) {
60        Node* node = root;
61        for (char c : word) {
62            int i = c - 'a';
63            if (node->children[i] == nullptr) {
64                node->children[i] = new Node();
65            }
66            node = node->children[i];
67        }
68        if (node->value < 0) {
69            node->value = index++;
70        }
71        return node->value;
72    }
73
74    // DFS to compute the minimum cost of transforming the source substring starting at index `i`
75    long long depthFirstSearch(int i) {
76        if (i >= sourceString.length()) {
77            return 0;
78        }
79        if (memoizationCache[i] != -1) {
80            return memoizationCache[i];
81        }
82        long long result = (sourceString[i] == targetString[i]) ? depthFirstSearch(i + 1) : kInf;
83        Node* pNode = root;
84        Node* qNode = root;
85        for (int j = i; j < sourceString.length(); ++j) {
86            pNode = pNode->children[sourceString[j] - 'a'];
87            qNode = qNode->children[targetString[j] - 'a'];
88            if (pNode == nullptr || qNode == nullptr) {
89                break;
90            }
91            if (pNode->value < 0 || qNode->value < 0) {
92                continue;
93            }
94            long long tempCost = graph[pNode->value][qNode->value];
95            if (tempCost < kInf) {
96                result = min(result, tempCost + depthFirstSearch(j + 1));
97            }
98        }
99        return memoizationCache[i] = result;
100    }
101};
102

1// Declaration for the Node type
2type Node = {
3    children: (Node | null)[];
4    value: number;
5};
6
7// Function to create a new Node with initialized values
8const createNode = (): Node => ({
9    children: Array(26).fill(null),
10    value: -1
11});
12
13// The global "root" node of the trie
14const root: Node = createNode();
15
16// Mapping from index to nodes
17let index: number = 0;
18
19// Memoization array for the DFS
20const memo: number[] = Array(100).fill(-1);
21
22// Function to insert a word into the trie and return the corresponding node value
23const insertWord = (word: string): number => {
24    let node: Node = root;
25    for (const char of word) {
26        const charIndex: number = char.charCodeAt(0) - 'a'.charCodeAt(0);
27        if (node.children[charIndex] === null) {
28            node.children[charIndex] = createNode();
29        }
30        node = node.children[charIndex]!;
31    }
32    if (node.value < 0) {
33        node.value = index++;
34    }
35    return node.value;
36};
37
38// The main minimumCost function definition
39function minimumCost(
40    source: string,
41    target: string,
42    original: string[],
43    changed: string[],
44    cost: number[],
45): number {
46    const originalLength = cost.length;
47    const sourceLength = source.length;
48    const graph: number[][] = Array.from({ length: originalLength << 1 }, () => Array(originalLength << 1).fill(Infinity));
49
50    // Fill the graph based on original and changed strings and their associated costs
51    for (let i = 0; i < originalLength; ++i) {
52        const fromNode: number = insertWord(original[i]);
53        const toNode: number = insertWord(changed[i]);
54        graph[fromNode][toNode] = Math.min(graph[fromNode][toNode], cost[i]);
55    }
56
57    // Apply the Floyd-Warshall algorithm to find all pairs shortest paths
58    for (let k = 0; k < index; ++k) {
59        for (let i = 0; i < index; ++i) {
60            for (let j = 0; j < index; ++j) {
61                graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
62            }
63        }
64    }
65
66    // The DFS function to be used in the minimumCost function
67    const depthFirstSearch = (i: number): number => {
68        if (i >= sourceLength) {
69            return 0;
70        }
71        if (memo[i] !== -1) {
72            return memo[i];
73        }
74        let result: number = source[i] === target[i] ? depthFirstSearch(i + 1) : Infinity;
75        let p: Node = root;
76        let q: Node = root;
77        for (let j = i; j < source.length; ++j) {
78            p = p.children[source[j].charCodeAt(0) - 'a'.charCodeAt(0)]!;
79            q = q.children[target[j].charCodeAt(0) - 'a'.charCodeAt(0)]!;
80            if (!p || !q) {
81                break;
82            }
83            if (p.value < 0 || q.value < 0) {
84                continue;
85            }
86            const t: number = graph[p.value][q.value];
87            result = Math.min(result, t + depthFirstSearch(j + 1));
88        }
89        return (memo[i] = result);
90    };
91
92    // Start the DFS from the first character
93    const answer: number = depthFirstSearch(0);
94
95    // Return the minimum cost or -1 if no valid transformation is possible
96    return answer >= Infinity ? -1 : answer;
97}
98