Count Prefix-Matching Simple Paths in a Labeled Graph

Problem Statement

You are given an undirected graph with n vertices numbered from 0 to n - 1. Each vertex i is labeled with a single uppercase letter given in the string labels (where labels[i] is the character at vertex i). The edges of the graph are provided in a 2D array edges, where each element [u, v] represents an undirected edge between vertex u and vertex v.

You are also given a query string target of length m.

A simple path of length k is a sequence of distinct vertices (v_1, v_2, ..., v_k) such that for every 1 <= i < k, there is an edge between v_i and v_{i+1}. The string spelled by this path is labels[v_1] + labels[v_2] + ... + labels[v_k].

Return an integer array counts of length m, where counts[i] is the number of distinct simple paths in the graph whose spelled string equals the prefix target[0...i] (1-indexed prefix of length i + 1). Two paths are considered distinct if their sequences of vertices are not identical.

Function Signature

def count_prefix_paths(n: int, edges: list[list[int]], labels: str, target: str) -> list[int]:
    pass

Examples

Example 1

Input:
n = 4
edges = [[0, 1], [1, 2], [2, 3], [1, 3]]
labels = "ABAC"
target = "ABA"

Output: [2, 2, 2]

Explanation:
- Prefix "A" (length 1): Paths are [0] and [2]. Count = 2.
- Prefix "AB" (length 2): Paths are [0, 1] and [2, 1]. Count = 2.
- Prefix "ABA" (length 3): Paths are [0, 1, 2] and [2, 1, 0]. Count = 2.

Example 2

Input:
n = 3
edges = [[0, 1], [1, 2], [0, 2]]
labels = "AAA"
target = "AAAA"

Output: [3, 6, 6, 0]

Explanation:
- Prefix "A": [0], [1], [2] -> 3 paths.
- Prefix "AA": [0, 1], [1, 0], [1, 2], [2, 1], [0, 2], [2, 0] -> 6 paths.
- Prefix "AAA": [0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0] -> 6 paths.
- Prefix "AAAA": No simple path of length 4 exists in a 3-vertex graph -> 0 paths.

Constraints

• 1 <= n <= 14
• 0 <= len(edges) <= n * (n - 1) // 2
• edges[i].length == 2 with 0 <= edges[i][0], edges[i][1] < n and edges[i][0] != edges[i][1]
• The graph contains no duplicate edges.
• len(labels) == n
• 1 <= len(target) <= n
• labels and target consist only of uppercase English letters.