Javascript BFS & DFS


  • 0
    D

    BFS:

    var minMutation = function(start, end, bank) {
        var set = new Set(bank);
        if(!set.has(end))   return -1;
        var visited = new Set();
        visited.add(start);
        
        var q = [];
        q.push(start);
        var count = 1;
        while(q.length!==0){
            var size = q.length;
            
            for(var i = 0;i<size;i++){
                var a = q.shift();
                if(oneM(a,end)) return count;
                set.forEach((b)=>{
                    if(!visited.has(b) && oneM(a,b)){
                        q.push(b);
                        visited.add(b);
                    }
                });
            }
            
            count++;
        }
        return -1;
        
        
    };
    
    
    var oneM = function(a,b){
        var count = 0;
        for(var i =0;i<a.length;i++){
            if(a[i]!==b[i]){
                count++;
            }
        }
        return count===1;
    };
    

    DFS

    var minMutation = function(start, end, bank) {
        var set = new Set(bank);
        var visited = new Set();
        visited.add(start);
        if(!set.has(end))   return -1;
        var count = dfs(start);
        
        if(count === Number.MAX_VALUE)  return -1;
        return count;
        
        //@ return min_path
        
        function dfs(a){
            if(oneM(a,end)) return 1;
            
            var min = Number.MAX_VALUE;
            
            set.forEach((b)=>{
                if(oneM(a,b) && !visited.has(b)){
                    visited.add(b);
                    var c = dfs(b);
                    if(c!==Number.MAX_VALUE){
                        min = Math.min(min,c+1);
                    }
                    visited.delete(b);
                }
            });
            
            return min;
        }
    };
    
    
    var oneM = function(a,b){
        var count = 0;
        for(var i =0;i<a.length;i++){
            if(a[i]!==b[i]){
                count++;
            }
        }
        return count===1;
    };
    
    

Log in to reply
 

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