The city's underground subway stations are split into zones A, B, and C, due to differences in pricing, as shown below:
Balham
Bow Road
Green Park
Holbom
A
B
C
Mile End
Forest Hill
There are 3 types of tickets, sorted by their price in ascending order
There are 3 types of tickets, sorted by their price in <<< ascending order:
1. AB for travel within zones A, B, and between zones A and B in both directions;
2. BC for travel within zones B, C, and between zones B and C in both directions;
3. ABC for travel within zones A, B, C, and between zones A, B, and C in both directions, i.e. A->B->C and C->B->A.
You are given 3 arrays of strings stationsA stations, and stationsc, which contain the names of stations in that particular zone. You are also given 2 strings origin and destination which contain names of the starting and ending station for a trip. It is guaranteed that origin and destination are different. Your task is to return a strongwith the name of the cheapest ticket that wil
doesn't exist in any of the zones, return an empty string. It is guaranteed that the origin station always exists in one of the zones.
Note: You can assume that a direct route always exists. E.g., if you need to go from zone A to zone B, you shouldn't go via zone C.
Note: You are not expected to provide the most optimal solution, but a solution with time complexity not worse than o(max (stationsA.length, stationsB.length, stationsc.length) x max(origin.length, destination.length)) will fit within the execution time limit.
• For stationsA = ["Green Park", "Holborn"], stations = ["Mile End", "Bow Road"], stationsc = ["Forest Hill", "Balham"], origin = "Forest Hill", and destination = "Green Park", the output should be solution(stationsA, stationsß, stationsc, origin, destination) = "ABC"
Explanation: "Forest Hill" is in zone C and "Green Park" is in zone A, so only the ABC ticket would allow you to travel between them.
• For stationsA = ["Green Park", "Holborn"] "Bow Road"] stationsB = ["Mile End". stationsc = ["Forest Hill", "Balham"] origin = "Mile End" and destination Chon = "Bow Road", th should be solution(stationsA, stationsB, stationsc, origin, destination) = "AB"
Explanation: Both "Mile End" and "E Road" are in zone B, so you can use any ticket. Given that the "AB" ticket is the cheapest, the answer is "AB"
• For stationsA = ["Green Park"] stationsB = ["Mile End"] stationsc = ["Forest Hill"], origin = "Forest Hill" and destination = "Holborn", the output should be solution(stationsA, stations, stationsc, origin, destination) = ""Explanation: destination = "Holborn" is not present in any of the zones, so the answer is
nput/Output
• [execution time limit] 0.5 seconds (cpp)
• [memory limit] 1 GB
• [input] array.string stationsA
An array of strings containing names of subway stations.
Guaranteed constraints:
1 ≤ stationsA. length ≤ 1000
1 ≤ stationsA[i].length ≤ 50
⚫ [input] array.string stationsB• [input] array.string stationsB
An array of strings containing names of subway stations.
Guaranteed constraints: 1 ≤ stationsB.length ≤ 1000, 1 ≤ stations[i].length ≤ 50.
• [input] array.string stationsC
An array of strings containing names of subway stations.
Guaranteed constraints:
1 ≤ stationsc.length < 1000,
1 ≤ stationsc[i].length ≤ 50.
• [input] string origin• [input] string origin
A non-empty string that contains the name the origin subway station.
Guaranteed constraints:
1 ≤ origin.length ≤ 50
• [input] string destination
A non-empty string that contains the name of the destination subway station.
Guaranteed constraints:
1 ≤ destination.length ≤ 50.
destination = origin
• [output] string
Return the name of the cheapest ticket which allows you to travel between the origin stationoutput] string
Return the name of the cheapest ticket which allows you to travel between the origin station and the destination station, either: "AB", "BC" or "ABC". If the destination station doesn't exist in any of the zones, return an empty string