Lyft VO 面试真题解析：Reconstruct Route from Segments 路线重建

Legiana, a Lyft user, is reviewing his rides from a specific day. However, the application is not retrieving the complete data for the rides, and they are not listed in the correct order. Can you help resolve this issue?

You are given a list of routes where each route is represented as a pair of cities [start, end]. Each route connects two cities directly. Your task is to reconstruct the entire route from the given segments so that the route is continuous and includes all the segments exactly once.

Input

A list of lists named routes, where each element is a list of two strings [start, end] representing a direct route from start to end.

Output

A single string representing the reconstructed route with cities joined by -> .

Example 1

Given: [[SFO, LA], [NYC, SFO], [OAK, NYC]]
Result: "OAK -> NYC -> SFO -> LA"

Example 2

Given: [[A, E], [M, B], [C, A], [B, C]]
Result: "M -> B -> C -> A -> E"

Example 3

Given: [["Taco Bell", "Shake Shack"], ["Starbucks", "Wingstop"], ["Wingstop", "Taco Bell"]]
Output: Starbucks -> Wingstop -> Taco Bell -> Shake Shack

Example 4

Given: [[NYC, NJ]]
Result: "NYC -> NJ"

这道 Lyft VO 题的核心是根据一组有向路段还原完整路线。每个路段都是一个 <code>[start, end]</code>，表示从起点城市直接到终点城市。由于整条路线是连续的、且每个片段只使用一次，通常可以先统计每个城市的入度和出度，找出唯一的起点，然后顺着映射不断往后拼接，直到把所有城市串起来。单条路线时输出一个字符串；如果题目扩展到多条互相独立的路线，就需要把每条链分别重建，再按长度和起点字母序排序。