Minimum Cost to Convert String I - Leetcode 2976 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
9:24 - Coding Explanation

leetcode 2976

#neetcode #leetcode #python

[devnull]

Many times I come here just so that someone reads the description of the problem to me :))

[greatfate]

dijkstra is ultimate general tool but floyd mayweather is both easier to code and more efficient here

[dimitristolias]

An optimization to this solution would be to store the pairs of characters you need to convert and run dijkstra only on those pairs, terminating when you find min distance to target char.

[freecourseplatformenglish]

Solved it on my own. Dijkstra + memorization.

[pratyushthakur]

I solved it but was getting a tle this really helped

[AndrewKoulogeorge]

Definitely talk about Floyd for this solution !

[m.kamalali]

Thanks for the great effort,
I think Dijkstra could be optimised if we only push to the heap when the new cost is less than the minimum cost we already seen

[ashabyesrab]

How did you know that there could not be a cycle in the graph?

[saurabhgodse]

I have one doubt, where are we checking min cost if we reach same node again ?

[deepaksngh]

u better use flyod warshall, less complex and more easy with time complexity of O( 26^3 )

[jaiveersingh]

Fyi Dijkstra's rhymes with "like straws", not "pick straws"

[immortal]

Time Complexity: O(ELog(V))
it is showing this time complexity on leetcode am I missing something and can someone explain

[moabd]

thanks you're the best!
but i hope that you depend less on python tricks next time, to apply the solution on all languages

[vietnguyenquoc]

My dumbass brain did think of looping dikjstra, but somehow I thought it woukd be nsquare or more so. Darn it need to improve the complexity calculation

[BayernRocks]

Please re consider the neetcode fees (for Indians it's way too high)🙏🙏🙏🙏🙏

[saruhasan]

class Solution {
private static Map<Character, Integer> dijkstra(char src, Map<Character, List<Pair<Character, Integer>>> adj) {
Comparator<Pair<Integer, Character>> comparator = new Comparator<>() {
@Override
public int compare(Pair<Integer, Character> p1, Pair<Integer, Character> p2) {
return Integer.compare(p1.getKey(), p2.getKey());
}
};
Queue<Pair<Integer, Character>> heap = new PriorityQueue<>(comparator);
heap.add(new Pair<Integer, Character>(0, src));

Map<Character, Integer> min_cost_map = new HashMap<>();

while(!heap.isEmpty()) {
Pair<Integer, Character> pair = heap.poll();
int cost = (int)pair.getKey();
char node = (char)pair.getValue();

if {
continue;
}
min_cost_map.put(node, cost);

List<Pair<Character, Integer>> neighbors = adj.get(node);

if(neighbors != null) {
for(Pair<Character, Integer> nei_pair : neighbors) {
char nei = (char)nei_pair.getKey();
int nei_cost = (int)nei_pair.getValue();
heap.add(new Pair<Integer, Character>(nei_cost + cost, nei));
}
}
}

return min_cost_map;
}

public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
Map<Character, List<Pair<Character, Integer>>> adj = new HashMap<>();
for(int i = 0; i < cost.length; i++) {
{
adj.put(original[i], new ArrayList<>());
}
adj.get(original[i]).add(new Pair<Character, Integer>(changed[i], cost[i]));
}

Map<Character, Map<Character, Integer>> min_cost_maps = new HashMap<>();
for(int i = 0; i < source.length(); i++) {
char src = source.charAt(i);
{
;
} else {
min_cost_maps.put(src, dijkstra(src, adj));
}
}

long res = 0;



for(int i = 0; i < source.length(); i++) {
char src = source.charAt(i);
char dest = target.charAt(i);

if {
return -1;
}
res +=
}

return res;
}
}

Good luck 🙂

[chaitanyasharma]

djikstra giving TLE, please show floyd warshall solution