Share my clean Java code with comments [standard dfs]


  • 3
    M
    /*
        -- dfs
        -- JFK -- ATL
               |
               |- SFO
               |
               --
           hashmap <from, list_of_to>, and list_of_to should be sorted.
        -- 只要搜索到那个最小的结果即可停止
    */
    public class Solution {
        public List<String> findItinerary(String[][] tickets) {
            Map<String, List<String>> ticketInfo = new HashMap<>();
            for (String[] ticket: tickets) {
                List<String> destList = ticketInfo.get(ticket[0]);
                if (destList == null) {
                    destList = new ArrayList<String>();
                    ticketInfo.put(ticket[0], destList);
                }
                destList.add(ticket[1]);
            }
            for (List<String> destList: ticketInfo.values()) {
                Collections.sort(destList);
            }
            List<String> ans = new ArrayList<>();
            ans.add("JFK");
            dfs(ans, new ArrayList<String>(), ticketInfo, "JFK", tickets.length);
            return ans;
        }
        
        private void dfs(List<String> ans, List<String> cur, Map<String, List<String>> ticketInfo, String src, int targetSize) {
            if (ans.size() > 1) { return; }  // only need to find the smallest answer
            if (cur.size() == targetSize) {  // the smallest answer found
                ans.addAll(cur);
                return;
            }
            List<String> destList = ticketInfo.get(src);
            if (destList != null) {
                for (int i = 0; i < destList.size(); ++i) {
                    String dest = destList.remove(i);  // remove this dest so that it will not be visited again
                    cur.add(dest);
                    dfs(ans, cur, ticketInfo, dest, targetSize);
                    cur.remove(cur.size() - 1);
                    destList.add(i, dest);  // add this dest back in the list, at its original position
                }
            }
        }
    }

Log in to reply
 

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