Count Prefix Paths in a Character Graph
Google● MediumFULLTIMEPHONE 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.
Return an array counts of length target.length. For every index k, counts[k] is the number of matching paths that spell target.substring(0, k + 1).
Function
countPrefixPaths(labels: String, edges: int[][], target: String) → long[]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.
Example 2
labels = "ababa"edges = [[0,1],[1,2],[2,3],[3,4],[0,4]]target = "aba"return = [3,4,4]There are three starting a vertices and four directed a-b paths. Each of those four paths can extend to one unvisited a vertex, so the final count is also 4.
Example 3
labels = "aaaa"edges = [[0,1],[1,2],[2,3],[0,3]]target = "aaaa"return = [4,8,8,8]The graph is a four-cycle. Every vertex starts one path, every undirected edge contributes two ordered length-two paths, and each such direction extends uniquely around the cycle without revisiting a vertex.
Constraints
1 <= labels.length <= 10.1 <= target.length <= 10.labelsandtargetcontain only lowercase English letters.- Every edge is a pair
[u, v]with0 <= u < v < labels.length. - The edge list contains no duplicates, so the input is a simple undirected graph.