Shortest Path from an Encoded Graph
Intuit● MediumNEW GRADINTERNOAProblem statement
You are given an array of strings strArr that the source describes as modeling a non-looping Graph.
The array is organized as follows:
- The first element is the number of nodes
N, written as a string. - The next
Nelements are the node names. A node name may contain spaces, such asBrick StreetorMain Street. - Every remaining element describes one connection in the form
nodeA-nodeB. A connection works in both directions. The graph may contain no connections.
FastPrep practice interpretation: Here, non-looping means that a connection cannot join a node to itself. Cycles involving different nodes are allowed, as shown by the source examples.
Return the shortest path from the first listed node to the last listed node, joining the node names with hyphens. There will be only one shortest path. If no path connects the first and last nodes, return -1.
Function
shortestPath(strArr: String[]) → StringExamples
Example 1
strArr = ["4","A","B","C","D","A-B","B-D","B-C","C-D"]return = "A-B-D"The path A-B-D reaches the last listed node in two connections, which is shorter than going through C.
Example 2
strArr = ["7","A","B","C","D","E","F","G","A-B","A-E","B-C","C-D","D-F","E-D","F-G"]return = "A-E-D-F-G"The unique shortest route from A to G is A-E-D-F-G.
Example 3
strArr = ["5","A","B","C","D","F","A-B","A-C","B-C","C-D","D-F"]return = "A-C-D-F"Starting with A-C reaches F through D in three connections.
Example 4
strArr = ["4","X","Y","Z","W","X-Y","Y-Z","X-W"]return = "X-W"The direct connection X-W is the shortest route.
Constraints
- The encoded graph contains at least two nodes.
- Each connection joins two listed nodes and can be traversed in either direction.
- If a path exists, its shortest route is unique.
Source note: The two source slides show the full statement and the visible examples in order.