# Follow Up: If the starting point of the itinerary is unknown, how can we find the start airport?

• For example: the tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]], and how can we find the start airport, that is "JFK"

• Search Eular Circuits.

• @DriftlessHenry Thanks very much. Based on your reply, I find the solution:
If all vertices have even degree - choose any of them.
If there are exactly 2 vertices having an odd degree - choose one of them.
Otherwise no euler circuit or path exists.

``````    public List<String> findItinerary(String[][] tickets) {
if(tickets == null || tickets.length == 0 || tickets[0].length == 0) return res;
Map<String, PriorityQueue<String>> map = new HashMap<>();
Map<String, Integer> degree = new HashMap<>();
for(String[] ticket : tickets) {
if(!map.containsKey(ticket[0])) map.put(ticket[0], new PriorityQueue<String>());
map.get(ticket[0]).offer(ticket[1]);
degree.put(ticket[0], degree.getOrDefault(ticket[0], 0) + 1);
degree.put(ticket[1], degree.getOrDefault(ticket[1], 0) + 1);
}
String start = findStart(degree);
//System.out.println("Start Airport: " + start);
if(start.length() == 0) System.out.println("No path");
else dfs(res, map, start);
return res;
}

private void dfs(List<String> res, Map<String, PriorityQueue<String>> map, String airport) {
while(map.containsKey(airport) && map.get(airport).size() > 0) {
dfs(res, map, map.get(airport).poll());
}
}

private String findStart(Map<String, Integer> map) {
boolean allEven = true;
String[] res = new String[2];
int count = 0;
for(String s : map.keySet()) {
int val = map.get(s);
allEven = (val % 2 == 0) && allEven;
if(val % 2 == 1) res[count++] = s;
}
if(allEven || count == 2) return res[0];
else return "";
}
``````

• @mysun Exactly! I missed the information that JFK is always the starting city at first, so I tried to solve the problem in this way. Besides Eular Circuits, there are many other interesting circuits topics worth learning.

• @DriftlessHenry Yes, last time I also found an interview question about the Eulerian Cycle, if you are interested in, you can try it :)

Given a password box, its password is a four-digit number, we need to generate a sequence with minimum length to open the password box.

e.g. if the password is a 3-digit number, and it only contains 0 and 1, then the minimum-length sequence is 0 0 0 1 0 1 1 1 (0 0) , (0 0) means reusing the first and second digit in the sequence, because we can get all the combination: 000, 001, 010, 101, 011, 111, 110, 100,

(0 0 0) 1 0 1 1 1

0 (0 0 1) 0 1 1 1

0 0 (0 1 0) 1 1 1

0 0 0 (1 0 1) 1 1

0 0 0 1 (0 1 1) 1

0 0 0 1 0 (1 1 1)

0 0 0 1 0 1 (1 1 , 0) 0 0 1 0 1 1 1

0 0 0 1 0 1 1 (1 , 0 0) 0 1 0 1 1 1

We can see this sequence is the minimum-length sequence which contains all 3-digit number with 0 and 1.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.