golang 解法, 执行用时: 504 ms, 内存消耗: 7.8 MB, 提交时间: 2023-10-21 20:08:20

func mostSimilar(n int, roads [][]int, names []string, targetPath []string) []int {
    // targetPath最长是100，每个位置的可能性是100个城市
    // dp[i][j] 表示当targetPath的第i个位置是城市j的时候，的最短编辑距离
    // 最后求的是min(dp[len(targetPath)][j]), 其中j >= 0 && j < len(names)
    // 加上一个pre[i][j]表示前一个城市，记录路径
    // 这样的话复杂度可以降到range_i * range_j
    // ffreturn的解法确实很精巧，借鉴一下哈，谢谢啦
    // dp[i][j] = min(dp[i - 1][k] + (1: names[j] != targetPath[i])) 其中k到j（其实就是j到k）有边
    // 牛逼的人是靠持之以恒的刷题，一次次不会，一次次借鉴，重要的是不要burn out，不想刷就停下，长期主义
    
    am := getAdjMap(roads)
    dp := make([][]int, 0)
    pre := make([][]int, 0)
    maxNum := 101

    for i := 0; i < len(targetPath); i ++ {
        tmp := make([]int, 0)
        tmpPre := make([]int, 0)
        for j := 0; j < len(names); j ++ {
            tmp = append(tmp, maxNum)
            tmpPre = append(tmpPre, -1)
        }
        dp = append(dp, tmp)
        pre = append(pre, tmpPre)
    }

    for j := 0; j < len(names); j ++ {
        if targetPath[0] == names[j] {
            dp[0][j] = 0
        } else {
            dp[0][j] = 1 // 1个编辑距离
        }
    }

    for i := 1; i < len(targetPath); i ++ {
        for j := 0; j < len(names); j ++ {
            tmpCost := maxNum
            for cand, _ := range am[j] {
                curCost := dp[i - 1][cand]
                if targetPath[i] != names[j] { // 如果j不相等，那就加上一个编辑距离
                    curCost += 1
                }
                if curCost < tmpCost {
                    tmpCost = curCost
                    pre[i][j] = cand // 往前追路径
                }
            }
            dp[i][j] = tmpCost
        }
    }
    fmt.Printf("dp is %v, pre is %v \n", dp, pre)
    res := make([]int, 0)

    // 先找到min
    minIndex := -1
    minCost := maxNum
    for j := 0; j < len(names); j ++ {
        if dp[len(targetPath) - 1][j] < minCost {
            minIndex = j
            minCost = dp[len(targetPath) - 1][j]
        }
    }
    fmt.Printf("minCost is %d \n", minCost)
    // 这里是逆序的，从头部插入
    for i := len(targetPath) - 1; i >= 0; i -- {
        res = append([]int{minIndex}, res...)
        minIndex = pre[i][minIndex]
    }

    return res
}

func getEd(targetPath []string, cand []int, names []string) int {
    res := 0
    for i, city := range targetPath {
        if names[cand[i]] != city {
            res ++
        }
    }
    return res
}

// 注意，是双向可达
func getAdjMap(roads [][]int) map[int]map[int]bool {
    am := make(map[int]map[int]bool, 0)
    for _, r := range roads {
        _, e := am[r[0]]
        if !e {
            am[r[0]] = make(map[int]bool)
        }
        am[r[0]][r[1]] = true

        _, e1 := am[r[1]]
        if !e1 {
            am[r[1]] = make(map[int]bool)
        }
        am[r[1]][r[0]] = true
    }
    fmt.Printf("adj map is %v \n", am)
    return am
}

cpp 解法, 执行用时: 472 ms, 内存消耗: 118.2 MB, 提交时间: 2023-10-21 20:07:51

class Solution {
public:
    vector<int> mostSimilar(int n, vector<vector<int>>& roads, vector<string>& names, vector<string>& targetPath) {
        vector<int> dp(n);
        vector<string> paths(n);
        // build the graph
        vector<vector<int>> g(n);
        for (const vector<int>& road: roads) {
            g[road[0]].emplace_back(road[1]);
            g[road[1]].emplace_back(road[0]);
        }
        // buttom-up dp
        for (const string& city: targetPath) {
            vector<int> dp2(n, 100);
            vector<string> paths2(n);
            for (int i = 0; i < n; ++i)
                for (const int& j: g[i])
                    if (dp2[j] > dp[i] + (city != names[j])) {
                        dp2[j] = dp[i] + (city != names[j]);
                        paths2[j] = paths[i];
                        paths2[j] += j;
                    }
            swap(dp, dp2);
            swap(paths, paths2);
        }
        string& str = paths[min_element(dp.begin(), dp.end()) - dp.begin()];
        return vector<int>(str.begin(), str.end());
    }
};

python3 解法, 执行用时: 1768 ms, 内存消耗: 27.4 MB, 提交时间: 2023-10-21 20:07:13

class Solution:
    def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]:
        d=defaultdict(list)
        for a,b in roads:
            d[a].append(b)
            d[b].append(a)
            
        @functools.lru_cache(None)
        def dp(roadIdx,targetIdx):
            if targetIdx>=len(targetPath): return 0,[]
            mincost,minpath=min([dp(nxt,targetIdx+1) for nxt in d[roadIdx]],key=lambda x:x[0])
            return mincost+(names[roadIdx]!=targetPath[targetIdx]),[roadIdx]+minpath
            
        return min([dp(i,0) for i in range(n)],key=lambda x:x[0])[1]

java 解法, 执行用时: 113 ms, 内存消耗: 44.8 MB, 提交时间: 2023-10-21 20:06:50

class Solution {
    int n;
    Map<Integer, List<Integer>> G;
    String[] names;
    String[] targetPath;

    public List<Integer> mostSimilar(int n, int[][] roads, String[] names, String[] targetPath) {
        if (n == 0 || roads == null || names == null || targetPath == null) return new ArrayList<>();
        // 初始化
        this.n = n;
        this.names = names;
        this.targetPath = targetPath;
        int len = targetPath.length;
        
        // 建立查询字典<城市名字，id>
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < names.length; i++) {
            map.put(names[i], i);
        }

        // 建图
        buildGraph(roads);

        // distance[i][j] 位置 i 上选择城市 j 时，剩下的所有可能选择里的最小编辑距离。这是个memo dp。
        Integer[][] distance = new Integer[len][n];  

        // bestCity[i][j] 位置 i 上选择城市 j 时，下一个最优的邻居城市的id。这也是个memo dp。
        int[][] bestNextCity = new int[len][n];        

        // 找出最小距离, 第一个最优城市
        int totalMinDistance = Integer.MAX_VALUE;
        int startCity = 0;
        for (int i = 0; i < n; i++) {
            int dis = dfs(0, i, distance, bestNextCity);  // dfs找所有可能性
            if (dis < totalMinDistance) {
                totalMinDistance = dis;
                startCity = i;
            }
        }

        // 把最优路径填进 res
        List<Integer> res = new ArrayList<>();
        int idx = 0;
        while (idx < len) {
            res.add(startCity);
            startCity = bestNextCity[idx][startCity];
            idx++;
        }
        return res;
    }

    // 给定当前城市curCityID，当前城市以及之后路径的最优距离是多少？
    private int dfs(int curIdx, int curCityID, Integer[][] distance, int[][] bestNextCity) {
        if (curIdx == targetPath.length) return 0;

        // memo
        if (distance[curIdx][curCityID] != null) return distance[curIdx][curCityID];

        // curIdx上的距离
        int curCost = names[curCityID].equals(targetPath[curIdx]) ? 0 : 1;

        // curIdx之后的最小距离
        int minCost = Integer.MAX_VALUE;
        for (int neighbor : G.get(curCityID)) {
            int neighborCost = dfs(curIdx + 1, neighbor, distance, bestNextCity);
            if (neighborCost < minCost) {
                minCost = neighborCost;
                bestNextCity[curIdx][curCityID] = neighbor;
            }
        }

        // 把上面两项加起来
        curCost += minCost;

        // 存进memo
        distance[curIdx][curCityID] = curCost;

        return curCost;
    }

    private void buildGraph(int[][] roads) {
        G = new HashMap<>();
        for (int[] road : roads) {
            int a = road[0];
            int b = road[1];

            G.putIfAbsent(a, new ArrayList<>());
            G.putIfAbsent(b, new ArrayList<>());

            G.get(a).add(b);
            G.get(b).add(a);
        }
    }
}