← 返回 microsoft 的题目列表Order Records by Matching Start/End and Concatenate Payloads
类型：online_judge
Problem: Order Records by Matching Start/End and Concatenate Payloads
You are given a set of records. Each record contains:
start: a string
end: a string
payload: a string (can be treated as an ID or any text fragment)
The records originate from a sequence (or sequences) formed by chaining fragments: if record A has end == record B's start, then A should appear before B.
Task 1: Single-chain ordering and payload concatenation
Assuming all records form exactly one complete chain (no branches, no cycles, no missing links):
Order the records by the chaining rule
Concatenate payload in that order and output the resulting string
Example
Input records (shuffled):
(start="bbb", end="ccc", payload="1")
(start="aaa", end="bbb", payload="2")
(start="ccc", end="ddd", payload="3")
Output:
"213"
Constraints
1 <= n <= 2e5
start/end are non-empty strings
Target complexity close to O(n) (or O(n log n))
Test Cases
Input:
3
aaa bbb 2
bbb ccc 1
ccc ddd 3
Output:
213
Input:
1
aaa bbb X
Output:
X
Input:
4
x y a
a b b
b c c
y a d
Output:
adbc
Input:
3
a b 1
b c 2
c d 3
Output:
123
Input:
5
p q A
q r B
r s C
s t D
t u E
Output:
ABCDE
Example
Input
3
aaa bbb 2
bbb ccc 1
ccc ddd 3
Output
213