Count Prefix-Matching Simple Paths in a Labeled Graph
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an undirected graph whose vertices each carry one lowercase character and a query word. For every non-empty prefix of the word, count the distinct simple paths whose sequence of vertex labels equals that prefix. A path may start at any vertex, and paths with different vertex sequences are distinct. Return the counts in prefix order.
### Function Contract
Implement `count_prefix_paths(labels, edges, word) -> list[int]`, where `labels[i]` is vertex `i`'s character and `edges` contains undirected pairs `[u, v]`.
### Constraints
- `1 <= len(labels) <= 18` and `1 <= len(word) <= 18`.
- The graph is simple: no self-loops and no duplicate edges.
- A simple path cannot visit the same vertex twice.
- Counts fit in a signed 64-bit integer.
### Examples
- For labels `"roteoreote"`, edges `[[0,1],[0,2],[0,3],[1,4],[1,5],[3,6],[4,7],[5,8],[6,9]]`, and word `"trees"`, return `[2, 2, 1, 1, 0]`. The matching paths are `(2)` and `(8)` for `t`; `(2,0)` and `(8,5)` for `tr`; `(2,0,3)` for `tre`; and `(2,0,3,6)` for `tree`. No path spells `trees`.
- For one vertex labeled `a` and word `aa`, return `[1, 0]` because the vertex cannot be reused.
```hint Carry frontier states
After matching one prefix, extend only paths ending at a vertex adjacent to an unused vertex with the next required label.
```
```hint Remember visited vertices
The same endpoint can represent different valid states when the paths used different vertex sets.
```
### Edge Cases
- Several vertices may have the same label.
- The graph may be disconnected.
- Once a prefix count is zero, all longer prefix counts are also zero.
Quick Answer: Count distinct simple graph paths whose labels match every nonempty prefix of a query word. Paths may start anywhere but cannot revisit a vertex, so the task rewards subset-state search and careful counting over a small labeled graph.
Given a simple undirected graph whose vertices carry lowercase characters and a lowercase query word, count for each nonempty word prefix the distinct simple paths whose vertex-label sequence equals that prefix. A path may start anywhere, cannot reuse a vertex, and paths with different vertex sequences are distinct. Return counts in prefix order.
Constraints
- 1 <= len(labels) <= 18 and labels contains lowercase characters.
- 1 <= len(word) <= 18 and word contains lowercase characters.
- The undirected graph has no self-loops or duplicate edges.
- A path cannot reuse a vertex, and counts fit in a signed 64-bit integer.
Examples
Input: ('roteoreote', [[0, 1], [0, 2], [0, 3], [1, 4], [1, 5], [3, 6], [4, 7], [5, 8], [6, 9]], 'trees')
Expected Output: [2, 2, 1, 1, 0]
Explanation: This is the source example, including a zero count for the final prefix.
Input: ('a', [], 'aa')
Expected Output: [1, 0]
Explanation: The only vertex matches the first prefix but cannot be reused.
Hints
- Carry a frontier keyed by endpoint and visited-vertex mask.
- Store a multiplicity for each state because distinct vertex orders can reach the same mask and endpoint.