AC Java solution - DFS with TreeMap


  • 1
    C

    Is there a way to avoid using TreeMap?

    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            List<String> result = new ArrayList();
            if (tickets == null || tickets.length == 0) return result;
            
            Map<String, TreeMap<String, Integer>> map = new HashMap();
            
            for (String[] pair : tickets) {
                if (!map.containsKey(pair[0])) map.put(pair[0], new TreeMap());
                TreeMap<String, Integer> cache = map.get(pair[0]);
                cache.put(pair[1], cache.containsKey(pair[1]) ? cache.get(pair[1]) + 1 : 1);
            }
            dfs("JFK", map, result, tickets.length + 1);
            return result;
        }
        
        private boolean dfs(String curr, Map<String, TreeMap<String, Integer>> map, List<String> result, int size) {
            result.add(curr);
            if (result.size() == size) return true;
            if (map.containsKey(curr)) {
                TreeMap<String, Integer> children = map.get(curr);
    
                for (String next : children.keySet()) {
                    if (children.get(next) > 0) {
                        children.put(next, children.get(next) - 1);
                        boolean res = dfs(next, map, result, size);
                        if (res) return true;
                        children.put(next, children.get(next) + 1);
                    }
                }
            }
            result.remove(result.size() - 1);
            return false;
        }
    }

  • 0
    D

    I use TreeMap too~ let's not feel bad about it : )

    Alternatively you can sort the tickets first by "from" and then by "to" stably. Then use LinkedHashMap instead... you can also use LinkedList but need to be careful and remember the insert location..


Log in to reply
 

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