Minimum Cost to Convert String II solution and explanation

def minCostToConvert(source, target, original, changed, cost):
    n = len(source)
    m = len(original)
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(n):
        if dp[i] == float('inf'):
            continue
        for j in range(m):
            len_sub = len(original[j])
            if i + len_sub <= n and source[i:i+len_sub] == original[j]:
                new_section = changed[j]
                if target[i:i+len_sub] == new_section:
                    dp[i + len_sub] = min(dp[i + len_sub], dp[i] + cost[j])
    return dp[n] if dp[n] != float('inf') else -1

source = "abcd"
target = "acbe"
original = ["a", "b", "c", "c", "e", "d"]
changed = ["b", "c", "b", "e", "b", "e"]
cost = [2, 5, 5, 1, 2, 20]
print(minCostToConvert(source, target, original, changed, cost))

import java.util.*;

public class MinCostConversion {
    public static int minCostToConvert(String source, String target, String[] original, String[] changed, int[] cost) {
        int n = source.length();
        int m = original.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 0; i < n; ++i) {
            if (dp[i] == Integer.MAX_VALUE) continue;
            for (int j = 0; j < m; ++j) {
                int len = original[j].length();
                if (i + len <= n && source.substring(i, i + len).equals(original[j])) {
                    String newSection = changed[j];
                    boolean transformationPossible = target.contains(original[j]);
                    if (transformationPossible && target.substring(i, i + len).equals(newSection)) {
                        dp[i + len] = Math.min(dp[i + len], dp[i] + cost[j]);
                    }
                }
            }
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
    
    public static void main(String[] args) {
        String source = "abcd";
        String target = "acbe";
        String[] original = {"a", "b", "c", "c", "e", "d"};
        String[] changed = {"b", "c", "b", "e", "b", "e"};
        int[] cost = {2, 5, 5, 1, 2, 20};
        int result = minCostToConvert(source, target, original, changed, cost);
        System.out.println(result);
    }
}

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

int minCostToConvert(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {
    int n = source.size();
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    
    for (int i = 0; i < n; ++i) {
        if (dp[i] == INT_MAX)
            continue;
        for (int j = 0; j < original.size(); ++j) {
            int len = original[j].size();
            if (i + len <= n && source.substr(i, len) == original[j]) {
                string newSection = changed[j];
                bool transformationPossible = (target.find(original[j]) != string::npos);
                if (transformationPossible && target.substr(i, len) == newSection) {
                    dp[i + len] = min(dp[i + len], dp[i] + cost[j]);
                }
            }
        }
    }
    return dp[n] == INT_MAX ? -1 : dp[n];
}

int main() {
    string source = "abcd";
    string target = "acbe";
    vector<string> original = {"a","b","c","c","e","d"};
    vector<string> changed = {"b","c","b","e","b","e"};
    vector<int> cost = {2,5,5,1,2,20};
    int result = minCostToConvert(source, target, original, changed, cost);
    cout << result << endl;
    return 0;
}

function minCostToConvert(source, target, original, changed, cost) {
    let n = source.length;
    let dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 0; i < n; ++i) {
        if (dp[i] === Infinity) continue;
        for (let j = 0; j < original.length; ++j) {
            let len = original[j].length;
            if (i + len <= n && source.substring(i, i + len) === original[j]) {
                let newSection = changed[j];
                if (target.substring(i, i + len) === newSection) {
                    dp[i + len] = Math.min(dp[i + len], dp[i] + cost[j]);
                }
            }
        }
    }
    return dp[n] === Infinity ? -1 : dp[n];
}

let source = "abcd";
let target = "acbe";
let original = ["a", "b", "c", "c", "e", "d"];
let changed = ["b", "c", "b", "e", "b", "e"];
let cost = [2, 5, 5, 1, 2, 20];
console.log(minCostToConvert(source, target, original, changed, cost));

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minCostToConvert(char* source, char* target, char** original, char** changed, int* cost, int n, int m) {
    int dp[n+1];
    for (int i = 0; i <= n; i++)
        dp[i] = INT_MAX;
    dp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        if (dp[i] == INT_MAX) continue;
        for (int j = 0; j < m; j++) {
            int len = strlen(original[j]);
            if (i + len <= n && strncmp(&source[i], original[j], len) == 0) {
                char newSection[101];
                strncpy(newSection, &source[i], len);
                newSection[len] = '\0';
                int transformationPossible = !!strstr(target, newSection);
                if (transformationPossible) {
                    strncpy(newSection, changed[j], len);
                    newSection[len] = '\0';
                    if (strncmp(&target[i], newSection, len) == 0)
                        dp[i + len] = dp[i + len] < dp[i] + cost[j] ? dp[i + len] : dp[i] + cost[j];
                }
            }
        }
    }
    return dp[n] == INT_MAX ? -1 : dp[n];
}

int main() {
    char* source = "abcd";
    char* target = "acbe";
    char* original[] = {"a","b","c","c","e","d"};
    char* changed[] = {"b","c","b","e","b","e"};
    int cost[] = {2,5,5,1,2,20};
    int n = strlen(source);
    int m = 6;
    int result = minCostToConvert(source, target, original, changed, cost, n, m);
    printf("%d\n", result);
    return 0;
}

using System;

class Program {
    public static int MinCostToConvert(string source, string target, string[] original, string[] changed, int[] cost) {
        int n = source.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;

        for (int i = 0; i < n; ++i) {
            if (dp[i] == int.MaxValue) continue;
            for (int j = 0; j < original.Length; ++j) {
                int len = original[j].Length;
                if (i + len <= n && source.Substring(i, len) == original[j]) {
                    string newSection = changed[j];
                    if (target.Substring(i, len) == newSection) {
                        dp[i + len] = Math.Min(dp[i + len], dp[i] + cost[j]);
                    }
                }
            }
        }
        return dp[n] == int.MaxValue ? -1 : dp[n];
    }

    public static void Main() {
        string source = "abcd";
        string target = "acbe";
        string[] original = {"a","b","c","c","e","d"};
        string[] changed = {"b","c","b","e","b","e"};
        int[] cost = {2,5,5,1,2,20};
        var result = MinCostToConvert(source, target, original, changed, cost);
        Console.WriteLine(result);
    }
}

def minCostToConvertDFS(source, target, original, changed, cost):
    memo = {}
    m = len(source)

    def dfs(idx):
        if idx >= m:
            return 0
        if idx in memo:
            return memo[idx]
        min_cost = float('inf')
        for j in range(len(original)):
            len_sub = len(original[j])
            if idx + len_sub <= m and source[idx:idx+len_sub] == original[j]:
                new_section = changed[j]
                if target[idx:idx+len_sub] == new_section:
                    total_cost = dfs(idx + len_sub)
                    if total_cost != float('inf'):
                        min_cost = min(min_cost, cost[j] + total_cost)
        memo[idx] = min_cost
        return min_cost

    result = dfs(0)
    return -1 if result == float('inf') else result

source = "abcd"
target = "acbe"
original = ["a", "b", "c", "c", "e", "d"]
changed = ["b", "c", "b", "e", "b", "e"]
cost = [2, 5, 5, 1, 2, 20]
print(minCostToConvertDFS(source, target, original, changed, cost))

class Node {
    children: (Node | null)[] = Array(26).fill(null);
    v: number = -1;
}

function minimumCost(
    source: string,
    target: string,
    original: string[],
    changed: string[],
    cost: number[],
): number {
    const m = cost.length;
    const n = source.length;
    const g: number[][] = Array.from({ length: m << 1 }, () => Array(m << 1).fill(Infinity));
    const root: Node = new Node();
    let idx: number = 0;
    const f: number[] = Array(n).fill(-1);
    const insert = (w: string): number => {
        let node: Node = root;
        for (const c of w) {
            const i: number = c.charCodeAt(0) - 'a'.charCodeAt(0);
            if (node.children[i] === null) {
                node.children[i] = new Node();
            }
            node = node.children[i] as Node;
        }
        if (node.v < 0) {
            node.v = idx++;
        }
        return node.v;
    };

    const dfs = (i: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        let res: number = source[i] === target[i] ? dfs(i + 1) : Infinity;
        let p: Node = root;
        let q: Node = root;
        for (let j = i; j < source.length; ++j) {
            p = p.children[source[j].charCodeAt(0) - 'a'.charCodeAt(0)] as Node;
            q = q.children[target[j].charCodeAt(0) - 'a'.charCodeAt(0)] as Node;
            if (p === null || q === null) {
                break;
            }
            if (p.v < 0 || q.v < 0) {
                continue;
            }
            const t: number = g[p.v][q.v];
            res = Math.min(res, t + dfs(j + 1));
        }
        return (f[i] = res);
    };

    for (let i = 0; i < m; ++i) {
        const x: number = insert(original[i]);
        const y: number = insert(changed[i]);
        g[x][y] = Math.min(g[x][y], cost[i]);
    }

    for (let k = 0; k < idx; ++k) {
        for (let i = 0; i < idx; ++i) {
            if (g[i][k] >= Infinity) {
                continue;
            }
            for (let j = 0; j < idx; ++j) {
                g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    const ans: number = dfs(0);
    return ans >= Infinity ? -1 : ans;
}

type Node struct {
	children [26]*Node
	v        int
}

func newNode() *Node {
	return &Node{v: -1}
}

func minimumCost(source string, target string, original []string, changed []string, cost []int) int64 {
	inf := 1 << 60
	root := newNode()
	idx := 0
	m := len(cost)
	g := make([][]int, m<<1)
	for i := range g {
		g[i] = make([]int, m<<1)
		for j := range g[i] {
			g[i][j] = inf
		}
		g[i][i] = 0
	}
	insert := func(w string) int {
		node := root
		for _, c := range w {
			i := c - 'a'
			if node.children[i] == nil {
				node.children[i] = newNode()
			}
			node = node.children[i]
		}
		if node.v < 0 {
			node.v = idx
			idx++
		}
		return node.v
	}
	for i := range original {
		x := insert(original[i])
		y := insert(changed[i])
		g[x][y] = min(g[x][y], cost[i])
	}
	for k := 0; k < idx; k++ {
		for i := 0; i < idx; i++ {
			if g[i][k] >= inf {
				continue
			}
			for j := 0; j < idx; j++ {
				g[i][j] = min(g[i][j], g[i][k]+g[k][j])
			}
		}
	}
	n := len(source)
	f := make([]int, n)
	for i := range f {
		f[i] = -1
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if i >= n {
			return 0
		}
		if f[i] >= 0 {
			return f[i]
		}
		f[i] = inf
		if source[i] == target[i] {
			f[i] = dfs(i + 1)
		}
		p, q := root, root
		for j := i; j < n; j++ {
			p = p.children[source[j]-'a']
			q = q.children[target[j]-'a']
			if p == nil || q == nil {
				break
			}
			if p.v < 0 || q.v < 0 {
				continue
			}
			f[i] = min(f[i], dfs(j+1)+g[p.v][q.v])
		}
		return f[i]
	}
	ans := dfs(0)
	if ans >= inf {
		ans = -1
	}
	return int64(ans)
}

use std::cmp::min;

struct Node {
    children: [Option<Box<Node>>; 26],
    v: i32,
}

impl Node {
    fn new() -> Self {
        Self {
            children: std::array::from_fn(|_| None),
            v: -1,
        }
    }
}

impl Solution {
    pub fn minimum_cost(
        source: String,
        target: String,
        original: Vec<String>,
        changed: Vec<String>,
        cost: Vec<i32>,
    ) -> i64 {
        let inf: i64 = 1 << 60;
        let mut root = Box::new(Node::new());
        let mut idx: usize = 0;
        let m = cost.len();
        let n = m << 1;

        let mut g = vec![vec![inf; n]; n];
        for i in 0..n {
            g[i][i] = 0;
        }

        let mut insert = |w: &str, root: &mut Box<Node>, idx: &mut usize| -> usize {
            let mut node: &mut Box<Node> = root;
            for c in w.bytes() {
                let i = (c - b'a') as usize;
                if node.children[i].is_none() {
                    node.children[i] = Some(Box::new(Node::new()));
                }
                node = node.children[i].as_mut().unwrap();
            }
            if node.v < 0 {
                node.v = *idx as i32;
                *idx += 1;
            }
            node.v as usize
        };

        for i in 0..m {
            let x = insert(&original[i], &mut root, &mut idx);
            let y = insert(&changed[i], &mut root, &mut idx);
            g[x][y] = min(g[x][y], cost[i] as i64);
        }

        for k in 0..idx {
            for i in 0..idx {
                if g[i][k] >= inf {
                    continue;
                }
                for j in 0..idx {
                    let v = g[i][k] + g[k][j];
                    if v < g[i][j] {
                        g[i][j] = v;
                    }
                }
            }
        }

        let s = source.into_bytes();
        let t = target.into_bytes();
        let len = s.len();
        let mut f: Vec<Option<i64>> = vec![None; len];

        fn dfs(
            i: usize,
            s: &[u8],
            t: &[u8],
            root: &Box<Node>,
            g: &Vec<Vec<i64>>,
            f: &mut Vec<Option<i64>>,
            inf: i64,
        ) -> i64 {
            if i >= s.len() {
                return 0;
            }
            if let Some(v) = f[i] {
                return v;
            }
            let mut res = if s[i] == t[i] {
                dfs(i + 1, s, t, root, g, f, inf)
            } else {
                inf
            };
            let mut p: Option<&Box<Node>> = Some(root);
            let mut q: Option<&Box<Node>> = Some(root);
            for j in i..s.len() {
                p = p.and_then(|x| x.children[(s[j] - b'a') as usize].as_ref());
                q = q.and_then(|x| x.children[(t[j] - b'a') as usize].as_ref());
                if p.is_none() || q.is_none() {
                    break;
                }
                let pv = p.unwrap().v;
                let qv = q.unwrap().v;
                if pv < 0 || qv < 0 {
                    continue;
                }
                let c = g[pv as usize][qv as usize];
                if c < inf {
                    let v = c + dfs(j + 1, s, t, root, g, f, inf);
                    if v < res {
                        res = v;
                    }
                }
            }
            f[i] = Some(res);
            res
        }

        let ans = dfs(0, &s, &t, &root, &g, &mut f, inf);
        if ans >= inf { -1 } else { ans }
    }
}