Solve shortest and label-similar paths

Part A — Unweighted shortest path: You are given an undirected, unweighted graph with vertices labeled 0..n-1 and an edge list. Given start node s and target node t, return both the length and one actual shortest path (as a list of vertices). If no path exists, return an empty list. Discuss your algorithm and its time and space complexity. Part B — Path matching a label sequence with minimal mismatches: Each vertex i has a string label name[i]. Given a sequence target[0..m-1] of labels, find a path v0..v_{m-1} such that consecutive vertices are adjacent in the graph and the number of indices i where name[v_i] != target[i] is minimized. Return one optimal vertex sequence. Explain your approach, how you reconstruct the path, and analyze complexity for n up to 10^4, edges up to 10^4, and m up to 10^3.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Unweighted Shortest Path with Reconstruction

You are given an undirected, unweighted graph with n vertices labeled 0..n-1 and an edge list edges. Given a start node s and a target node t, return a two-element list [length, path] where length is the number of edges on a shortest path from s to t and path is one actual shortest path as a list of vertices from s to t. If s == t, return [0, [s]]. If no path exists, return [-1, []].

Use breadth-first search (BFS) from s: BFS visits vertices in non-decreasing distance order, so the first time you reach t you have a shortest path. Track a parent pointer for each visited vertex and walk it back from t to s to reconstruct the path. With n vertices and E edges, BFS runs in O(n + E) time and O(n + E) space (adjacency list + visited/parent arrays + queue).

Constraints

• 1 <= n <= 10^4
• 0 <= number of edges <= 10^4
• edges[i] = [u, v] with 0 <= u, v < n, u != v
• 0 <= s, t < n
• The graph is undirected and unweighted; it may be disconnected and may contain cycles.

Examples

Example 1

Input: (6, [[0,1],[1,2],[2,3],[1,4],[4,5],[5,3]], 0, 3)
Output: [3, [0, 1, 2, 3]]

Explanation: Shortest route from 0 to 3 is 0->1->2->3 of length 3; the alternative 0->1->4->5->3 has length 4.

Example 2

Input: (4, [[0,1],[2,3]], 0, 3)
Output: [-1, []]

Explanation: Vertices 0 and 3 lie in different connected components, so no path exists.

Hints

1. BFS explores nodes in order of increasing distance, so the first time you dequeue (or reach) t you already have a shortest path — no need to keep searching.
2. Store a parent[] pointer when you first discover each node; to rebuild the path, walk parent[] from t back to s and reverse the result.
3. Handle s == t (length 0, path [s]) and the disconnected case (return [-1, []]) explicitly.

Path Matching a Label Sequence with Minimal Mismatches

Each vertex i of an undirected graph (n vertices, edge list edges) has a string label name[i]. Given a target sequence target[0..m-1] of labels, find a walk v0, v1, ..., v_{m-1} such that consecutive vertices are adjacent in the graph (edge between v_{i-1} and v_i) and the number of indices i where name[v_i] != target[i] is minimized. Return one optimal vertex sequence (length m). Vertices may repeat.

This is dynamic programming over positions (the same shape as LeetCode 1548). Let dp[i][v] be the minimum number of mismatches for a walk of length i+1 that ends at vertex v and is aligned with target[0..i]. Base case: dp[0][v] = (name[v] != target[0]). Transition: dp[i][v] = min over neighbors u of dp[i-1][u]) + (name[v] != target[i]). The answer cost is min_v dp[m-1][v]; reconstruct the path with a parent table. To make the output deterministic, sort each adjacency list and scan vertices in ascending order, keeping the first minimizing choice. Complexity is O(m * (n + E)) time because each position relaxes every edge once.

Constraints

• 1 <= n <= 10^4
• 0 <= number of edges <= 10^4
• 1 <= m <= 10^3 (length of target)
• name has length n; target has length m; labels are arbitrary strings
• Consecutive vertices in the returned walk must be adjacent; vertices may repeat.
• If m >= 2 and the graph has no edges, no valid walk of length m exists; return an empty list.

Examples

Example 1

Input: (5, [[0,1],[1,2],[2,3],[3,4]], ['a','b','c','d','e'], ['a','b','c'])
Output: [0, 1, 2]

Explanation: Vertices 0,1,2 have labels a,b,c matching target exactly along the path edges 0-1 and 1-2, giving 0 mismatches.

Example 2

Input: (3, [[0,1],[1,2]], ['x','y','z'], ['a','b','c'])
Output: [0, 1, 0]

Explanation: No label matches any target, so every valid walk costs 3 mismatches; [0,1,0] is one optimal walk (edges 0-1 and 1-0).

Hints

1. Think position-by-position: dp[i][v] = cheapest way to align target[0..i] onto a walk ending at vertex v. Initialize dp[0][v] with just the mismatch at v.
2. The transition only looks at neighbors of v in the previous position: dp[i][v] = min(dp[i-1][u] for u adjacent to v) + (name[v] != target[i]).
3. Keep a parent[i][v] = the u that achieved the minimum, then walk it back from the best end vertex to reconstruct one optimal sequence. Sort adjacency lists for a deterministic tie-break.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Part A — Unweighted shortest path: You are given an undirected, unweighted graph with vertices labeled 0..n-1 and an edge list. Given start node s and target node t, return both the length and one actual shortest path (as a list of vertices). If no path exists, return an empty list. Discuss your algorithm and its time and space complexity. Part B — Path matching a label sequence with minimal mismatches: Each vertex i has a string label name[i]. Given a sequence target[0..m-1] of labels, find a path v0..v_{m-1} such that consecutive vertices are adjacent in the graph and the number of indices i where name[v_i] != target[i] is minimized. Return one optimal vertex sequence. Explain your approac...

Recommended Approach

Model each reachable configuration as a graph state and choose the traversal by edge cost: BFS for unweighted shortest paths, Dijkstra for non-negative weighted paths, or topological DP for DAGs. Track visited states at the correct granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.