Count Prefix Paths in a Character Graph
GoogleFULLTIMEPHONE SCREENProblem statement
You are given a simple undirected graph. Its vertices are indexed from 0 to labels.length - 1, and labels[i] is the character stored at vertex i. The array edges contains every undirected edge.
For a non-empty prefix of target, a matching path is an ordered sequence of distinct vertices whose consecutive vertices share an edge and whose labels spell that prefix in order. Two paths are distinct when their ordered vertex sequences differ. Because vertices may not repeat within one path, traversing a cycle back to an already used vertex is not allowed.
Examples
Example 1
labels = "treetr"edges = [[0,1],[1,2],[2,3],[4,5]]target = "trees"return = [2,2,1,1,0]Vertices 0 and 4 spell t. The paths [0,1] and [4,5] spell tr. Only [0,1,2] extends to tre, and only [0,1,2,3] extends to tree. No path spells trees.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
Pro subscription, billed yearly — or $19 month-to-month. Cancel anytime.