Minimum Cost to Convert String I - Leetcode 2976 - Python

[@devnull711]

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

[@abhinavchoukse2357]

dude it's Floyd Warshall Algorithm... floyd mayweather is a boxer 😂😂

[@salim444]

Floyd Mayweather be punching them vertices up 😂. edit: سيف النار اقوى من فلويد 😅

[@roderickli6505]

i thought it was v^3 compared to djstra wouldnt djstra be better?

[@tuandino6990]

​@@roderickli6505 if you terminate dijkstra early it might beat floyd mayweather

[@freecourseplatformenglish2829]

Solved it on my own. Dijkstra + memorization.

[@dimitristolias2551]

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.

[@pratyushthakur8478]

I solved it but was getting a tle this really helped

[@freecourseplatformenglish2829]

Yes, the length of string is long so you need to memorize the repeated calls.

[@pratyushthakur8478]

@@freecourseplatformenglish2829 I wasn’t using dijkstra tho I had a recursive dfs like function

[@AndrewKoulogeorge]

Definitely talk about Floyd for this solution !

[@rostislav_engineer]

Thanks for this video!

[@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

[@DreamZdsb19]

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

[@MuscleTeamOfficial]

Thx mr

[@jaiveersingh5538]

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

[@pastori2672]

easy af 💯

[@vikneshcs4824]

How tc is o(n+m)

[@saurabhgodse8482]

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

[@theich4303]

If we reach the same node again, the check in line 13 will be True and we continue with the next node. The heap guarantees that if we reach a node for the first time, it will be with the lowest cost.

[@ashabyesrab5166]

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

[@saruhasan9145]

class Solution { private static Map dijkstra(char src, Map adj) { Comparator comparator = new Comparator() { @Override public int compare(Pair p1, Pair p2) { return Integer.compare(p1.getKey(), p2.getKey()); } }; Queue heap = new PriorityQueue(comparator); heap.add(new Pair(0, src)); Map min_cost_map = new HashMap(); while(!heap.isEmpty()) { Pair pair = heap.poll(); int cost = (int)pair.getKey(); char node = (char)pair.getValue(); if (min_cost_map.containsKey(node)) { continue; } min_cost_map.put(node, cost); List neighbors = adj.get(node); if(neighbors != null) { for(Pair nei_pair : neighbors) { char nei = (char)nei_pair.getKey(); int nei_cost = (int)nei_pair.getValue(); heap.add(new Pair(nei_cost + cost, nei)); } } } return min_cost_map; } public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) { Map adj = new HashMap(); for(int i = 0; i < cost.length; i++) { if(!adj.containsKey(original[i])) { adj.put(original[i], new ArrayList()); } adj.get(original[i]).add(new Pair(changed[i], cost[i])); } Map min_cost_maps = new HashMap(); for(int i = 0; i < source.length(); i++) { char src = source.charAt(i); if(min_cost_maps.containsKey(src)) { ; } else { min_cost_maps.put(src, dijkstra(src, adj)); } } long res = 0; System.out.println(min_cost_maps); for(int i = 0; i < source.length(); i++) { char src = source.charAt(i); char dest = target.charAt(i); if (!min_cost_maps.get(src).containsKey(dest)) { return -1; } res += (int)min_cost_maps.get(src).get(dest); } return res; } } Good luck 🙂

[@ParodyCSEDept]

How about Floyd Warshall algorithm?

[@tranminhquang4541]

I think the floyd warshall algo is only used when we know the depth of the tree with root being the source . That's just my guess. Correct me if I'm wrong!

[@jamestwosheep]

@@tranminhquang4541 I managed to use Floyd-Warshall on this problem - that algo is useful whenever you need the shortest path from every node to every other node. So as far as I understand it, I don't think there's any size/depth or start/source limitations on it. But the algo does take O(V^3) time complexity to run (V being the number of verticies/nodes), which isn't too bad for this problem because V = 26 in worst case, so O(26^3) is still O(1). Edit: I should also mention that if there's no valid path from node A to node B, Floyd-Warshall will simply give you an infinite cost to go between those 2 nodes (assuming Infinity is how you decide to mark an invalid path). Long story short, kzbin.info/www/bejne/aoC0lnargb6dY5Y has a really good explanation on Floyd Warshall.

[@manimtirkey861]

@@jamestwosheep Agreed! the moment you encounter an infinite cost you can break the loop and return -1.

[@tranminhquang4541]

@@jamestwosheep I'm wrong then . Sorry !

[@jamestwosheep]

@@tranminhquang4541 Oh please, no need to be sorry! I'm on my own algorithms study journey at the moment and this stuff is hard! But, I've found that being wrong and understanding the misunderstanding has been a pretty good way to learn so far. So please, don't be sorry, and good luck to you for your own studies! :D

[@immortal4091]

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

[@fancypants6062]

🤩

[@anshdholakia714]

another graph problem :fire:

[@Empire-jx5wk]

Graph 😮

[@vietnguyenquoc4948]

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

[@BayernRocks2020]

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

[@moabd7575]

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

[@fancypants6062]

He explained how to write it without "tricks" in the video. Also, these "tricks" are just how to write something in 1 line instead of 3 lines. There are some crazy one-liners that are possible in python, but he doesn't use those, he keeps things very basic so that it can be easily converted.

[@chaitanyasharma6270]

djikstra giving TLE, please show floyd warshall solution

[@chaitanyasharma6270]

my gjikstra solution public class Solution { Dictionary g=new Dictionary(); public long MinimumCost(string source, string target, char[] original, char[] changed, int[] cost) { for(int i=0;i

[@chaitanyasharma6270]

i memoized my solution it worked public class Solution { Dictionary g=new Dictionary(); Dictionary dp; public long MinimumCost(string source, string target, char[] original, char[] changed, int[] cost) { dp=new Dictionary(); for(int i=0;i

[@陳冠霖-q6y]

@@chaitanyasharma6270 you can run dijkstra algo at most 26 times, using dp to memorize and avoiding repeat compution if duplicate.