| 33 | return dist; |
| 34 | } |
| 35 | public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) { |
| 36 | //adj list for directed graph |
| 37 | long adj[][] = new long[26][26]; |
| 38 | for(int i=0;i<26;i++){ |
| 39 | Arrays.fill(adj[i],Integer.MAX_VALUE); |
| 40 | } |
| 41 | int n = original.length; |
| 42 | for(int i=0;i<n;i++){ |
| 43 | int from = original[i]-97; |
| 44 | int to = changed[i]-97; |
| 45 | long converstionCost = cost[i]; |
| 46 | //since there are multiple values, take min. |
| 47 | adj[from][to] = Math.min(adj[from][to], converstionCost); |
| 48 | } |
| 49 | int m = source.length(); |
| 50 | long matrix[][] = new long[26][26]; |
| 51 | HashSet<Integer> uniqueSrc = new HashSet<>(); |
| 52 | //apply Dijkstra's Algorithm |
| 53 | for(int i=0;i<m;i++){ |
| 54 | int src = source.charAt(i)-97; |
| 55 | if(!uniqueSrc.contains(src)){ |
| 56 | matrix[src] = dijkstra(src,adj); |
| 57 | uniqueSrc.add(src); |
| 58 | } |
| 59 | } |
| 60 | long minCost = 0; |
| 61 | for(int i=0;i<m;i++){ |
| 62 | int src = source.charAt(i)-97; |
| 63 | int dest = target.charAt(i)-97; |
| 64 | if(matrix[src][dest] == Integer.MAX_VALUE){ |
| 65 | return -1; |
| 66 | } |
| 67 | minCost += matrix[src][dest]; |
| 68 | } |
| 69 | return minCost; |
| 70 | } |
| 71 | } |