Minimum Cost to Convert String I - Leetcode 2976 - Python

  Рет қаралды 10,399

NeetCodeIO

NeetCodeIO

Күн бұрын

Пікірлер: 42
@devnull711
@devnull711 4 ай бұрын
Many times I come here just so that someone reads the description of the problem to me :))
@greatfate
@greatfate 4 ай бұрын
dijkstra is ultimate general tool but floyd mayweather is both easier to code and more efficient here
@abhinavchoukse2357
@abhinavchoukse2357 4 ай бұрын
dude it's Floyd Warshall Algorithm... floyd mayweather is a boxer 😂😂
@salim444
@salim444 4 ай бұрын
Floyd Mayweather be punching them vertices up 😂. edit: سيف النار اقوى من فلويد 😅
@roderickli6505
@roderickli6505 4 ай бұрын
i thought it was v^3 compared to djstra wouldnt djstra be better?
@tuandino6990
@tuandino6990 4 ай бұрын
​@@roderickli6505 if you terminate dijkstra early it might beat floyd mayweather
@dimitristolias2551
@dimitristolias2551 4 ай бұрын
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.
@freecourseplatformenglish2829
@freecourseplatformenglish2829 4 ай бұрын
Solved it on my own. Dijkstra + memorization.
@pratyushthakur8478
@pratyushthakur8478 4 ай бұрын
I solved it but was getting a tle this really helped
@freecourseplatformenglish2829
@freecourseplatformenglish2829 4 ай бұрын
Yes, the length of string is long so you need to memorize the repeated calls.
@pratyushthakur8478
@pratyushthakur8478 4 ай бұрын
@@freecourseplatformenglish2829 I wasn’t using dijkstra tho I had a recursive dfs like function
@AndrewKoulogeorge
@AndrewKoulogeorge 4 ай бұрын
Definitely talk about Floyd for this solution !
@m.kamalali
@m.kamalali 4 ай бұрын
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
@rostislav_engineer
@rostislav_engineer 4 ай бұрын
Thanks for this video!
@MuscleTeamOfficial
@MuscleTeamOfficial 4 ай бұрын
Thx mr
@jaiveersingh5538
@jaiveersingh5538 4 ай бұрын
Fyi Dijkstra's rhymes with "like straws", not "pick straws"
@saurabhgodse8482
@saurabhgodse8482 4 ай бұрын
I have one doubt, where are we checking min cost if we reach same node again ?
@theich4303
@theich4303 4 ай бұрын
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.
@pastori2672
@pastori2672 4 ай бұрын
easy af 💯
@fancypants6062
@fancypants6062 4 ай бұрын
🤩
@ashabyesrab5166
@ashabyesrab5166 4 ай бұрын
How did you know that there could not be a cycle in the graph?
@vikneshcs4824
@vikneshcs4824 23 күн бұрын
How tc is o(n+m)
@Empire-jx5wk
@Empire-jx5wk 4 ай бұрын
Graph 😮
@vietnguyenquoc4948
@vietnguyenquoc4948 4 ай бұрын
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
@immortal4091
@immortal4091 4 ай бұрын
Time Complexity: O(ELog(V)) it is showing this time complexity on leetcode am I missing something and can someone explain
@ParodyCSEDept
@ParodyCSEDept 4 ай бұрын
How about Floyd Warshall algorithm?
@tranminhquang4541
@tranminhquang4541 4 ай бұрын
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
@jamestwosheep 4 ай бұрын
@@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
@manimtirkey861 4 ай бұрын
@@jamestwosheep Agreed! the moment you encounter an infinite cost you can break the loop and return -1.
@tranminhquang4541
@tranminhquang4541 4 ай бұрын
@@jamestwosheep I'm wrong then . Sorry !
@jamestwosheep
@jamestwosheep 4 ай бұрын
@@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
@anshdholakia714
@anshdholakia714 4 ай бұрын
another graph problem :fire:
@saruhasan9145
@saruhasan9145 4 ай бұрын
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 🙂
@BayernRocks2020
@BayernRocks2020 4 ай бұрын
Please re consider the neetcode fees (for Indians it's way too high)🙏🙏🙏🙏🙏
@moabd7575
@moabd7575 4 ай бұрын
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
@fancypants6062 4 ай бұрын
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
@chaitanyasharma6270 4 ай бұрын
djikstra giving TLE, please show floyd warshall solution
@chaitanyasharma6270
@chaitanyasharma6270 4 ай бұрын
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
@chaitanyasharma6270 4 ай бұрын
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
@陳冠霖-q6y 4 ай бұрын
@@chaitanyasharma6270 you can run dijkstra algo at most 26 times, using dp to memorize and avoiding repeat compution if duplicate.
Count Number of Teams - Leetcode 1395 - Python
17:29
NeetCodeIO
Рет қаралды 13 М.
If people acted like cats 🙀😹 LeoNata family #shorts
00:22
LeoNata Family
Рет қаралды 23 МЛН
coco在求救? #小丑 #天使 #shorts
00:29
好人小丑
Рет қаралды 30 МЛН
FOREVER BUNNY
00:14
Natan por Aí
Рет қаралды 31 МЛН
How I would learn Leetcode if I could start over
18:03
NeetCodeIO
Рет қаралды 695 М.
Edit Distance - Dynamic Programming - Leetcode 72 - Python
21:00
2 Keys Keyboard - Leetcode 650 - Python
17:37
NeetCodeIO
Рет қаралды 15 М.
Most Beautiful Item for Each Query - Leetcode 2070 - Python
17:17
Subarray Sums Divisible by K - Leetcode 974 - Python
16:41
NeetCodeIO
Рет қаралды 18 М.
5 Useful F-String Tricks In Python
10:02
Indently
Рет қаралды 330 М.
Combination Sum II - Leetcode 40 - Python
15:25
NeetCodeIO
Рет қаралды 19 М.
Learn JavaScript - Full Course for Beginners
3:26:43
freeCodeCamp.org
Рет қаралды 18 МЛН
Ugly Number II - Leetcode 264 - Python
15:17
NeetCodeIO
Рет қаралды 15 М.
If people acted like cats 🙀😹 LeoNata family #shorts
00:22
LeoNata Family
Рет қаралды 23 МЛН