Find an A-B-Plus-C Path with Two A Predecessors
Google● HardNEW GRADPHONE SCREENProblem statement
A directed graph has a label A, B, or C on every vertex.
Find a path whose first vertex is labeled A, followed by one or more B vertices, and whose final vertex is labeled C. Additionally, the first B vertex on the path must have incoming edges from at least two distinct A-labeled vertices.
Return a valid path with the fewest vertices. Break ties by lexicographically smaller vertex-index sequence. Return an empty array when none exists.
Function
findABPlusCPath(labels: String, edges: int[][]) → int[]Examples
Example 1
labels = "AABBC"edges = [[0,2],[1,2],[2,3],[3,4]]return = [0,2,3,4]B vertex 2 has A predecessors 0 and 1; the lexicographically smaller start A is 0.
Example 2
labels = "ABBC"edges = [[0,1],[1,2],[2,3]]return = []The first B has only one A predecessor.
Example 3
labels = "AABC"edges = [[0,2],[1,2],[2,3]]return = [0,2,3]One B between A and C satisfies B-plus.
Constraints
1 <= labels.length <= 500.0 <= edges.length <= 10000.- Labels contain only A, B, and C; edges contain valid distinct vertices.