Leetcode 854 图的bfs应用超时

来源：1-5 大厂面试为什么总考算法？

甲骨文_0001

2022-09-21

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var kSimilarity = function(s1, s2) {

    const Len = s1.length;

    let queue = [ [s1, 0] ]; // bfs队列, [顶点，目前的步数]
    let visited = {}; // 顶点访问查找表
    visited[s1] = true;

    // bfs
    while( queue.length > 0 ){

        let [ nowStr, step ] = queue.shift(); // 从队列中取出一个顶点进行考察

        if( nowStr == s2 ){
            return step;
        }

        // 取邻居, 通过双重for循环对字符串nowStr对调任意两个索引处得到的值进行分析
        for( let i = 0; i < Len; i ++ ){
            for( let j = i + 1; j < Len; j ++ ){
                let newStr = swap( nowStr, i, j );
                if( !visited[newStr] ){ // 未访问过再添加进queue中
                    queue.push( [ newStr, step + 1 ] );
                    visited[newStr] = true;
                }
            } // for j
        } // for i
        

    } // end while queue.length > 0

    return -1;
};

// 根据字符串 str, 调换索引i, j后得到的新字符串
function swap( str, i, j ){
    let arr = str.split(''); // 切成数组
    let t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    return arr.join(''); // 交换完对数组再拼接回去
}

老师，854是今天的每日一题，其实就是一道图的bfs求最短路径的题目，我用JS写了下，在第9个用例上就时间超时了，我想我写的代码思路应该是对的，是不是还是由于js的语言特性导致超时了，老师，帮我看看哈：）
图片描述

写回答

1回答

liuyubobobo

2022-09-21

已采纳

我不很确定 C++ 这么写会不会超时。但是这个逻辑是可以优化的。

在 BFS 的过程中，每次下一个状态，不需要任意取两个索引交换。因为我们的目标是 s2，且索引之间的交换没有限制。所以我们完全可以每次找到当前 nowStr 和 s2 不同的第一个索引（target_index），然后只解决这个索引的问题（找到 target_index 后的一个索引 i，使得 nowStr[i] == s2[target_index]，交换 i 和 target_index）。而更绕远的状态不需要遍历。（相当于做了剪枝）。具体可以参考下面的代码。

以下代码是我基于你的代码的修改。我实验是可以 ac 的：

var kSimilarity = function(s1, s2) {
    
    const Len = s1.length;
    
    let queue = [ [s1, 0] ]; // bfs队列, [顶点，目前的步数]
    let visited = {}; // 顶点访问查找表
    visited[s1] = true;
    
    // bfs
    while( queue.length > 0 ){
        
        let [ nowStr, step ] = queue.shift(); // 从队列中取出一个顶点进行考察
        if( nowStr == s2 ){
            return step;
        }
        
        // 找到针对 nowStr，最早和 s2 不同的索引 target_index，先解决这个索引的问题
        let target_index = 0;
        for(; target_index < Len; target_index ++)
            if(nowStr[target_index] != s2[target_index]) break;
        
        // 下面的状态转移从 O(Len^2) 变成了 O(Len)
        // 因为你的 swap 创建了一个新的字符串，是很耗时的操作，
        // 所以这个 for 因为只有在 if 条件下才执行后续的逻辑，节省的时间要比 O(Len) 高
        for( let i = target_index + 1; i < Len; i ++ ){
            if(nowStr[i] == s2[target_index]){
                let newStr = swap( nowStr, i, target_index);
                if( !visited[newStr] ){ // 未访问过再添加进queue中
                    queue.push( [ newStr, step + 1 ] );
                    visited[newStr] = true;
                }
            }
        }
        
    } // end while queue.length > 0
    return -1;
};

// 根据字符串 str, 调换索引i, j后得到的新字符串
function swap( str, i, j ){
    let arr = str.split(''); // 切成数组
    let t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
    return arr.join(''); // 交换完对数组再拼接回去
}

==========

上面这个代码理论上还能优化，比如我们是在 bfs 中每次从 0 遍历求出当前 nowStr 的 target_index，但实际上 target_index 可以作为状态的一部分存储。从一个状态转移到另一个状态，target_index 只会增加，所以不需要从 0 遍历。等等。但因为这个问题数据量不大，我也不确定这样做实际效果。反正这样已经能 ac 了。

继续加油！：）

liuyubobobo

甲骨文_0001

了解了。谢谢你的信息：）

2022-09-21

共4条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

查看课程

相似问题

BoBo老师好，您play-leetcode上的286号问题 Walls and Gates好像代码超时了