LeetCode#332重排行程DFS递归解法BUG调试求助

问题背景 #

LeetCode第332题是一道图论类的欧拉路径求解问题，要求返回字典序最小的行程序列。采用DFS回溯思路实现代码后，第一个单路径测试用例可正常通过，但多分支测试用例返回结果不符合预期。

核心问题点 #

• 机场列表未排序
  listAirports函数仅按机票出现顺序收集机场，没有做字典序排序，导致DFS遍历时优先访问了先出现的SFO，而非字典序更小的ATL，是输出结果不符合预期的直接原因。
• 回溯逻辑错误
  使用itinerary = itinerary.slice(0,itinerary.length - 1)回溯行程数组时，该操作会生成新数组赋值给局部变量，并不会修改上层递归传入的原行程数组，会导致后续遍历逻辑错误。
• 字典序比较函数逻辑错误
  • 调试打印语句参数写错，将第二个参数错误写为list1，导致日志输出异常
  • 字典序判断逻辑写反：else if (list2[i] > list1[i])成立时说明list1字典序更小，代码错误返回了list2，完全倒置了判断逻辑。

修改方案 #

1. 修正机场收集逻辑，新增排序 #

var listAirports = function(tickets) {
    var airports = [];
    for (var i = 0; i < tickets.length; i++) {
        var ticket = tickets[i];
        if (airports.indexOf(ticket[0]) === -1) {
            airports.push(ticket[0]);
        }
        if (airports.indexOf(ticket[1]) === -1) {
            airports.push(ticket[1]);
        }
    }
    airports.sort(); // 新增字典序排序
    return airports;
}

2. 修正回溯时的行程处理逻辑 #

// 删掉原有的 itinerary = itinerary.slice(0,itinerary.length - 1);
itinerary.pop(); // 直接修改原数组

3. 修正字典序比较函数 #

var lexMin = function(list1, list2) {
    console.log('lexMin('+list1+','+list2+')'); // 修正参数打印
    if (list1.length !== list2.length) {
        return list1.length < list2.length ? list1 : list2;
    } else {
        for (var i = 0; i < list1.length; i++) {
            if (list1[i] < list2[i]) {
                return list1;
            } else if (list1[i] > list2[i]) { // 修正判断条件
                return list2;
            }
        }
        return list1;
    }
}

内容的提问来源于stack exchange，提问作者GNG