Solution URL

https://leetcode.com/submissions/detail/413573185/
代码

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        //ans: https://www.youtube.com/watch?v=QEVAJjp5ikU
        //corner case
        if(tickets == null || tickets.size() == 0) return null;

        Map<String, List<String>> map = new HashMap<>();
        int n = tickets.size() + 1;
        List<String> res = new ArrayList<>();
        //对结果集初始化
        res.add("JFK");

        //用hashmap将start和destination存起来
        for(List<String> ticket: tickets){
            String key = ticket.get(0);

            //如果没有这个start，则先初始化
            if(!map.containsKey(key)){
                map.put(key, new ArrayList<String>());
            }

            //将k-v对存起来
            map.get(key).add(ticket.get(1));
        }

        //将所有value排序
        for(List<String> list: map.values()){
            Collections.sort(list);
        }

        //DFS 若DFS可行，则返回结果集
        if(dfs(res, "JFK", n, map)) return res;

        //不能连通
        return null;
    }

    public boolean dfs(List<String> res, String start, int n, Map<String, List<String>> map){
        //出口：遍历过所有的ticket，形成连通
        if(res.size() == n) return true;

        //map中没有这个start
        if(!map.containsKey(start)) return false;

        //有start,拿到dest;遍历所有destination，使用dfs
        List<String> dest = map.get(start);
        for(int i = 0; i < dest.size(); i++){
            String destination = dest.get(i);
            dest.remove(i);
            res.add(destination);
            if(dfs(res, destination, n, map)) return true;
            //回溯
            res.remove(res.size() - 1);
            dest.add(i, destination);
        }

        return false;
    }
}
Problem 332

Solution URL

代码

CATALOG

FEATURED TAGS
