Fewest Board Switches to Travel Between Two Pins via Shared Boards

A content platform groups pins into themed boards. Each board has a name and a list of pins, and the same pin can appear on several boards. For example, a pin for one city can sit on both a travel board and a food board.

You start on the pin start and want to reach the pin end. While you stand on a pin, you may move to any other pin on any board that contains your current pin. The only way to get from one board to another is through a pin that belongs to both.

The score of a trip is the number of times you switch boards. Return the minimum score from start to end.

Function Signature

def min_board_switches(boards: dict[str, list[str]], start: str, end: str) -> int:

Rules

• A route is a sequence of boards b_1, b_2, ..., b_m with m >= 1 such that start is on b_1, end is on b_m, and every two consecutive boards share at least one pin. The score of the route is m - 1. Return the minimum score over all routes.
• If start == end, return 0.
• If start and end are both on some common board, return 0, because no switch is needed.
• If no route exists, return 0. This includes the case where start or end is on no board at all. A result of 0 therefore covers both "no switch needed" and "unreachable".
• The answer is a single integer, so it is unique. Board names and pin ids are compared as exact strings.

Constraints

• 1 <= len(boards) <= 10^4
• Each board's list has between 1 and 10^4 pins, and a pin appears at most once in any single board's list.
• The total number of pin entries across all boards is at most 2 * 10^5.
• Board names, pin ids, start and end are non-empty strings of at most 30 characters, drawn from lowercase English letters, digits and underscores.
• start and end do not have to appear on any board.
• The returned value is between 0 and len(boards) - 1.

Examples

Example 1

boards = {
    "travel": ["california", "new_york", "washington"],
    "food":   ["new_york", "sichuan_cuisine", "cantonese_cuisine"],
    "sports": ["tennis", "basketball", "california"],
}
start = "california"
end = "cantonese_cuisine"
Output: 1

california is on travel and sports, and cantonese_cuisine is only on food. No single board holds both pins. travel and food share new_york, so the route travel -> food needs one switch.

Example 2

boards = {"a": ["p1", "p2"], "b": ["p2", "p3"], "c": ["p3", "p4"], "d": ["p5", "p6"]}
start = "p1"
end = "p4"
Output: 2

The best route is a -> b -> c. It switches boards at p2 and again at p3.

Example 3

boards = {"a": ["p1", "p2"], "b": ["p2", "p3"], "c": ["p3", "p4"], "d": ["p5", "p6"]}
start = "p1"
end = "p6"
Output: 0

Board d shares no pin with a, b or c, so p6 cannot be reached from p1.