Given a graph whose nodes are 3-letter words and an array of 3-letter words. Find a path in the graph such that the difference b/w words in the path and given array is minimum.
We are given 2 APIs which work for this graph:
class Graph {
/**
* Get all neighbors of a node.
*/
Set<String> getNeighbors(String node);
/**
* Get a list of all nodes in no particular order.
*/
Set<String> listAllNodes();
}
Consider a graph G: Test Graph
Example 1:
Input: G, arr = [AAA, BBB, CCC, DDD] Output: 2 Explanation: The path [AAA, BBC, CCD, DDD] is closest to given array. In path, BBC differs from BBB by 1 and CCD differs from CCC by 1 hence answer is 1 + 1 = 2. Example 2:
Input: G, arr = [AAA, CCC, AAA, BBD] Output: 3 Explanation: The path [AAA, BBC, AAA, BBC] is closest to given array. In path, BBC differs from CCC by 2 and BBC differs from BBD by 1 hence answer is 2 + 1 = 3.
Notice that we can visit the same node multiple times.
I can only think of a backtracking solution, is there a more optimal way to compute the answer? Thanks in advance :)
Expected Time complexity?
As it was an interview the excepted time complexity was not mentioned.But an improvement over brute solution was expected
You can use dp here. Let the number of nodes in graph be $$$V$$$ and number of edges be $$$E$$$ and length of array be $$$n$$$.
Let $$$dp[u][i]$$$ represent the minimum cost of a path which starts at node $$$u$$$ in the graph and the index $$$i$$$ in the given array.(Ie the best path for subarray $$$i...n$$$ which starts at node $$$u$$$ in the graph). The dp recurrence is given by
$$$dp[u][i]=min(dp[v][i+1])+dissimilarity(u,array[i])$$$ where $$$v$$$ iterate over all neighbours of $$$u$$$. The minimum cost will be stored in some $$$dp[u][1]$$$.
Base case is $$$dp[u][n]=dissimilarity(u,array[n])$$$
Time complexity is O(n*(V+E))
I don't have much practice in dp on graphs so I have a few questions :
Or if you have some link where I can learn dp on graphs from, that would be helpful. I already understand how tree dp works, but have very little understanding on how the idea is extended on graphs. Thank you
can u tell, from where you have started dp on tree ? means any blog or tutorial or fundamental problem of it ? can you please suggest !!
This should be a good place to start
A good recommendation when stuck at these situations is to simply write a brute force solution and then try to memoize it.