Give each unique string in <code>original</code> and <code>changed</code> arrays a unique id. There are at most <code>2 * m</code> unique strings in total where <code>m</code> is the length of the arrays. We can put them into a hash map to assign ids.

We can pre-compute the smallest costs between all pairs of unique strings using Floyd Warshall algorithm in <code>O(m ^ 3)</code> time complexity.

Let <code>dp[i]</code> be the smallest cost to change the first <code>i</code> characters (prefix) of <code>source</code> into <code>target</code>, leaving the suffix untouched. We have <code>dp[0] = 0</code>. <code>dp[i] = min( dp[i - 1] if (source[i - 1] == target[i - 1]), dp[j-1] + cost[x][y] where x is the id of source[j..(i - 1)] and y is the id of target e[j..(i - 1)]) )</code>. If neither of the two conditions is satisfied, <code>dp[i] = infinity</code>.

We can use Trie to check for the second condition in <code>O(1)</code>.

The answer is <code>dp[n]</code> where <code>n</code> is <code>source.length</code>.