May I ask the time complexity for straightforward dfs?


  • 0
    B
    public class Solution {
        boolean found = false;
        public void dfs(HashMap<String, ArrayList<String>> map, int len, int target, String cur, List<String> res) {
            if (len == target) {
                res.add(cur);
                found = true;
                return;
            }
            if (!map.containsKey(cur)) return;
            ArrayList<String> list = map.get(cur);
            res.add(cur);
            for (int i = 0; i < list.size(); i++) {
                String next = list.remove(i);
                dfs(map, len + 1, target, next, res);
                list.add(i, next);
                if (found == true) return;
            }
            res.remove(res.size() - 1);
        }
        public List<String> findItinerary(String[][] tickets) {
            List<String> res = new ArrayList<String>();
            
            HashMap<String, ArrayList<String>> map = new HashMap();
            for (int i = 0; i < tickets.length; i++) {
                if (!map.containsKey(tickets[i][0])) {
                    map.put(tickets[i][0], new ArrayList<String>());
                }
                map.get(tickets[i][0]).add(tickets[i][1]);
            }
            for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) {
                Collections.sort(entry.getValue());
            }
            dfs(map, 0, tickets.length, "JFK", res);
            return res;
        }
    }
    

    I used straightforward dfs, I know that it is slower than the O(n) euclidian path solution but is this time complexity exponential? because in worst case, we need to go through each adjacent airport to find the itinerary right?


Log in to reply
 

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