Minimum Cost to Convert String I | Weekly Contest 377 | 2 Approaches | Leetcode 2976
79Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 42nd Video of our Playlist "Graphs : Popular Interview Problems".
In this video we will try to solve a very good problem on application of Shortest Path Graph Algorithms (Floyd Warshall & Dijkstra's) - Minimum Cost to Convert String I (Leetcode 2976).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Minimum Cost to Convert String I
Company Tags : will update soon
My solutions on Github(C++ & JAVA) :
Floyd Warshall - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Floyd%20Warshall/Minimum%20Cost%20to%20Convert%20String%20I.cpp
Dijkstra's Algo - https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Dijkstra'a%20Based%20Problems/Minimum%20Cost%20to%20Convert%20String%20I.cpp
Leetcode Link : https://leetcode.com/problems/minimum-cost-to-convert-string-i/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Approach-1 Summary(Floyd Warshall) : The FloydWarshall function initializes 2D vector distances to represent the minimum costs between characters. It then iterates through the character replacements, updating the corresponding distances in the matrix. Subsequently, it applies the Floyd-Warshall algorithm to compute the shortest paths between all pairs of characters. The minimumCost function utilizes the distances computed by FloydWarshall to find the minimum cost of transforming the source string into the target string based on the specified character replacements. It iterates through each character position, accumulating the costs of necessary replacements. If there is no valid transformation for a character pair, it returns -1. Otherwise, it returns the total minimum cost of the transformation.
Approach-2 Summary : The dijkstra function implements Dijkstra's algorithm to compute the shortest paths from a given source character to all other characters in the graph represented by an adjacency list. It uses a priority queue to select the next node with the smallest distance and updates the distances accordingly. The minimumCost function utilizes the adjacency list constructed from the character replacements to find the minimum cost of transforming the source string into the target string. It applies Dijkstra's algorithm for each unique character in the original vector, updating the distances matrix. Then, it iterates through each character position, accumulating the costs of necessary replacements. If there is no valid transformation for a character pair, it returns -1. Otherwise, it returns the total minimum cost of the transformation.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa