Minimum Cost to Convert String I - Leetcode 2976 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum cost to convert string we're given five parameters in this problem so I'm really just going to focus on the example the idea is that we're given two strings one is source and one is Target and we want to convert every character from The Source string into the corresponding character in the Target string now these first pair of characters are the same so we don't really need to do anything but next we have B we want to convert it into C and we want to know what's the minimum cost to do that and we want to do that for every single pair of characters in both strings now how do you calculate the cost well that's what the next three parameters are for so I know the order is kind of jumbled but at least they're kind of in the same spot here so this is saying here that to change a into B the cost is going to be two this is saying to change B into C the cost is going to be five etc etc we just kind of keep going like that so when we're asking here what's the cost to change B into C well in this case it looks like there's only one direct way to change B into C but it could have technically been possible that there is another way suppose that we could change B into uh let's say a and then suppose we can change a into C now that's not possible I don't think in this example it looks like there's only one character that can actually land on C but imagine that there was some something like this and let's say that the cost to change B to a was 1 and a to c was also one then it's actually possible to change B to a with a total cost of two so we kind of have to consider that edge case and you might already know where I'm going here the information like the direct links here from one character to another that's not necessarily enough we have to consider the entire path does this start to seem like a graph problem to you because it is and obviously these edges have weights so what these three last parameters actually tell us is that for us to know what's the minimum cost to change one character into another it's not a straightforward answer but we can change these three parameters and build a connected might not necessarily be connected but it's going to be a directed graph with some weights if we have all that information first we build the graph and then we kind of consider how we could solve the problem though if your mind is thinking in terms of what the shortest path could be you're definitely on the right track and given that the edges have weights it's not going to be a simple breath for search it's going to be a Dix's breath for search so AKA Dix's algorithm because it's pretty much a breath for search with a priority q but let's first just build this graph so I'm going to start just going Pair by pair let's say a goes to b b goes to c c can go back to b c can also go to to e e can also go to B so I might have not drawn this in the best order but we're almost done it looks like we have another character D it can go into e okay so the graph is going to look something like this I'll add the weights now so the first one is going to be two this one is going to be five this one is also going to be five this one is going to be one e to B is going to be two and D to e is going to be 20 so this is the graph now let's go through the source and Target string so the first two characters are already the same so shortest path from a to itself will be zero what about B to C well from here now what are we going to do like what kind of traversal do you think we should run well we want to know in this graph what is the shortest path to C and when we say shortest path we're not counting the number of edges we're counting the total weight of each Edge aka the cost so in this case it's pretty simple um just B to C that's going to be five next we get a C to B so from here back to B that's also five or actually is it let's see actually cuz I don't think that's going to take us to the right answer let's see so C we can either go here like that's five but like I said dixis is like a breath for search except it's augmented so from here we're going to look at the two choices we have we can go here or here of course we're going to be greedy and pick the path with the least cost so okay for now we're going from C to e this is where we're at so far so the total cost to reach here was one so now our choices are either take this path of five or take this path of two but we also have to include the one that we've added so far so this path total it would cost three to get to B which is obviously less than this path so definitely we're going to take that one so actually the total cost from C to B the minimum cost is going to be three so so far I think we have five plus three and then the last question is D to e and from here it looks like there's only one way to reach there there's only one outgoing Edge from D so there's not another possible path so this is 20 add that in total looks like we get 28 and it does look like I did my math correctly we got the right solution so this is the whole idea behind the problem looks like it's going to be a dictra week um in terms of the time complexity I guess the max possible size of the graph so first of all let me cover two edge cases it might be possible that it's not possible to convert one character into another what that would mean is there's no path from one character to another so for example if we wanted to say from D to a I don't think there's a path from D to a because it doesn't look like any Edge is incoming into a in that case if it's not possible to convert The Source string into the Target string in that case we're going to return negative 1 rather than returning the total cost so that's one Edge case the other thing is what's the time complexity of this well to build the adjacency list we're going to need extra memory and we're going to need to go through these parameters so this is kind of like the number of edges of our graph right for every pair of these we have an edge in our graph so whatever the size of these parameters is going to be let's call it um M let's say n is the length of these that's the graph size pretty much and traversing the graph is going to be the same right so now we're actually getting into something very interesting because there's multiple ways to implement the solution that I'm talking about one of them is going to be much more efficient than the other so this is very important please pay attention let's say m is the number of edges in the graph and let's say n is the size of these strings the way I talked about it a second ago right I said okay every time we go through like a pair of characters we're going to run dickas to find the shortest path from that character to the next character so in other words the time complexity would be n because that's how many pairs of characters we have times M which is what a Dix's traversal is going to be on this graph roughly right that's one possible way to implement the solution now is is there repeated work in that because think about the case where the length of these strings is actually massive they tell us though that there's only going to be lowercase characters so there's only going to be up to 26 distinct total characters it kind of is strange to run Dias n times for the length of the input rather than running it 26 times so consider this consider if we ran Dix's algorithm for every single character in the source string what it would do is Dix's algorithm tells us what's the shortest path from a to every other node in the graph so suppose we had that we'd probably store it in an array or a hashmap I'm probably going to use a hashmap but suppose we had that for a and then suppose we do that for b c d and e what's the time complexity of doing that well we're running Dix's algorithm not n times but in the worst case 26 times because we're going to do it for every distinct character in The Source string we don't want to run it multiple times for the same Source character it doesn't make sense to do that we're going to do that and then have a hashmap like up to 26 hash Maps I guess once we have all of that stored then it becomes pretty trivial for us to look in that hashmap well we'll have 26 of them so we'll need to first to figure out which one we want to look at so for a we'll look at the hashmap corresponding to lowercase a and then in that hashmap we'll say okay what's the cost of going from A to B and the hash map should be able to tell us that so this way we get the time complexity down to M * 26 but we still do have to Traverse this so let's put a plus n there and this of course is going to pretty much reduce to m + n now the size of each hash map is technically going to be 26 like each character could be mapped to another for the shortest path between them and we're going to have 26 hash Maps uh in the worst case for each character so this is still technically a constant it's kind of a big constant but it's still technically a constant but but the space complexity is going to come from the graph itself like the number of edges which I guess still in the worst case could it really be greater than 26 squar I mean I guess if we have duplicate edges but I was more thinking along the lines of the space complexity is going to be Big O of M because that's the number of edges we have but at this point I'm not even sure how to think about it I guess it depends on the constraints of the problem but anyways let's code it up so this was like the intuition I used uh to solve the problem I'm going to do a lot of like python tricks in the solution so I want to quickly mention that in case you don't understand anything I'm doing in the python Solution that's literally why I created this course CU I always got questions all the time so you'll literally see every single thing I might do some like Advanced Heap stuff you'll see that you can learn all about that in the Heap section we'll do a lot of dictionary stuff like default diction stuff and you can learn about that here so literally anything you could need about python is covered in this course first starting with building the adjacency list I'm going to create a default dictionary exactly for that where the default value is going to a list because there's going to be a bunch of directed edges in this what we want to do is figure out the character from the original string maps to this character and the cost of that is going to be this so we have to kind of go through three arrays that are of the same size simultaneously we could do that with a pointer but trust me it's going to be a lot more concise doing it this way and this is kind of a python technique so we're going to go through the source destination and the current cost of that pair and we're going to zip all three of those arrays original changed and cost so the value from this is going to be that the value from this is going to be that and the value from here is going to be that I also cover zip in the python for coding interviews course believe it or not we're going to map source to the destination again this is a directed Edge it only goes one way but we're not just going to add the destination we're going to add a pair so the second value is going to be the cost associated with that edge we could use two different hashmaps if we wanted to maybe in other languages it is easier to do that one hash might tell you the node and then the other hashm might tell you the cost but I prefer to do it this way because it's easier to do it in Python so next we're going to have that dixes algorithm which I'm actually not going to fill in I like to kind of see how we're going to use it so remember this dixes is all about returning the entire map so from this Source node to every other node that is reachable we're going to have a hashmap and it's going to store like the shortest path between all of them in terms of cost so what are we going to do well like I said we want to run Dix's algorithm for every single distinct character in The Source string trust me that's easier to do with something called dictionary comprehension I'll show you this is what it would look like without dictionary comprehension let's say for character in set of source I'm calling set on it to get only the distinct characters from it and then we would do something like this running Dias on that and that'll give us a hashmap and then we want to add that hashmap into another hashmap mapping this character to like the map that it's being returned from it will literally look easier when I show you how I do it with dictionary comprehension because it's pretty much the same exact logic just written differently so I'm going to say this I'm going to create a dictionary we're going to go through every character in Source every distinct character and we're going to map that character to the map that is returned by Dix's algorithm that's it that's exactly what this is doing and let's assign that to minimum cost Maps so every character is mapped to another map where that map will store the shortest paths so now we can use that like this I'm going to go through every pair of characters in The Source and Target string I'll call it uh for Source destination in zip The Source string and the Target string there's a couple things to consider we want to obviously sum the total cost to go from the source to the destination whatever the minimum cost happens to be and then we want to return that but don't forget about the edge case where it's not possible to reach the destination from The Source how would we know if that's the case though well first of all consider this minimum cost Maps given the source this is a hash map this hashmap stores the minimum costs to reach every other node so I want to check is destination a key in that hashmap if it's not so if not that then here I'm going to return 1 that means it's not possible to reach the destination from The Source otherwise I'm going to say this I'm going to get that and then I'm going to use the second key the destination CU we know it exists in here and so this should give us the cost to go from the source to the destination and we just want to add that cost to the result so we're pretty much almost done believe it or not if you know how to do Dix's algorithm like me you can probably get the rest of this done in like 60 seconds maybe 2 minutes well I guess I'll be explaining every line so it might take me a bit longer but with a heap we are going to initialize it with the source node but the first value we're going to put is the cost it takes to reach that Source node since we're starting here we consider that cost to be zero so now I'm going to put that there now what we want to do is build the hash map I'm going to call it minimum cost map I don't know if that's a good name for it or not considering we have a very similar name here that's the plural of that but anyways that's what we want to return the minimum cost map while our Heap is nonempty we're going to pop from it we're going to do Heap Q Heap pop from the Heap and we're going to get two values we're going to get the cost which goes first and then node which goes second because that's the order that we added them we added the cost first because we want that to be the key that tells us the priority of the values in this Heap now we're going to check if the node is already in the minimum cost map then we can probably skip it cuz it's already been processed otherwise we'll add it now we'll say this is the first time that we were were able to reach this node so therefore this was the shortest path to reach that node so we'll say the cost to reach this node is the cost that was popped here in addition we're going to go through all the neighbors of this node in the adjacency list um so we can do that like this but don't forget it's easy to forget even for me that in the adjacency list we didn't just add one value we added a pair of values so here we're going to get the neighbor's cost and the neighbor but actually I have the order backwards cuz we added the node and then we added the cost so let me fix that like this and now we have that next we're going to just push it to the Heap so Heap Q Heap push to the Heap a pair of values the second value is going to be the node itself so we can say that's the neighbor but the cost to reach this neighbor is going to be accumulated we want the total cost to reach this neighbor not just one Edge so we're going to take the current cost to reach this node and then add it to the current Edge of that neighbor so Cost Plus neighbor cost and I think that is the entire code I don't know what my computer was doing it was kind of bugging but this is I believe the entire code I know we used a lot of like python tricks and even just python fundamentals with the Heap but again I promise you I cover all of this in the python for coding interviews course and you can see that it works and it's pretty efficient thanks for watching and I'll see you soon