Please Help Me with My Always TLE javascript Solution


  • 0
    L

    I used BFS to solve this problem with a queue.
    I did all the optimizations I can think of.

    1. I used an adjacency matrix to store the relationships between nodes to avert repetition.
    2. I Saved the length of the first path I found, whenever the depth of another path was larger than it, I ignored that path.
    3. I Saved all the nodes of current layer and removed them when depth increasing to improve efficiency of further searches.
    4. I did't calculate the whole tree. My code would stop adding new nodes to the queue after finding the firt path and the whole program stops when the queue is empty.

    But my code always time out.


    Here comes the code, I have no idea which part is wrong...lol.

    function Queue(first) {
      this.queue = [{
        path: [0],
        word: first,
      }];
    }
    
    Queue.prototype.enque = function (elements) {
      this.queue = this.queue.concat(elements);
    };
    
    Queue.prototype.dequeue = function () {
      return this.queue.pop();
    };
    
    const getDifferenceNum = (source, target) => {
      const ret = source.filter((s, i) => s !== target[i]).length;
      return ret;
    };
    
    function Test(begin, end, list) {
      this.results = [];
      this.list = [begin, ...list];
      this.list = this.list.map(s => s.split(''));
      this.end = end.split('');
      this.queue = new Queue(begin.split(''));
      this.deep = Number.MAX_SAFE_INTEGER;
      this.removeRepitition();
      this.makeAdjacencyMatrix();
      this.currentLevel = 0;
      this.currentLevelElements = [];
      this.usedElements = [];
    }
    
    Test.prototype.makeAdjacencyMatrix = function () {
      const length = this.list.length;
      this.adjacency = [];
      let index = 0;
      while (index < length) {
        this.adjacency[index] = [];
        index += 1;
      }
    
      index = 0;
      while (index < length) {
        let innerIndex = index + 1;
        while (innerIndex < length) {
          if (getDifferenceNum(this.list[index], this.list[innerIndex]) === 1) {
            // making use of the symmetry of the adjacency matrix
            this.adjacency[index].push(innerIndex);
            this.adjacency[innerIndex].push(index);
          }
    
          innerIndex += 1;
        }
    
        index += 1;
      }
    };
    
    Test.prototype.removeRepitition = function () {
      const hash = {};
      const newList = [];
      this.list.forEach(l => {
        if (!hash[l]) {
          hash[l] = true;
          newList.push(l);
        }
      });
      this.list = newList;
    };
    
    Test.prototype.findChildren = function (parent) {
      const currentIndex = parent.path.slice(-1)[0];
      if (parent.path.length > this.currentLevel) {
        this.usedElements = this.usedElements.concat(this.currentLevelElements);
        this.currentLevelElements = [currentIndex];
        this.currentLevel = parent.path.length;
      } else {
        this.currentLevelElements.push(currentIndex);
      }
    
      const ret = this.adjacency[currentIndex].filter(l =>
        {
          return parent.path.find(p => p === l) === undefined
            && this.usedElements.find(p => p === l) === undefined;
        });
    
      return ret.map(r => (
        {
          word: this.list[r],
          path: [...parent.path, r],
        }
        ));
    };
    
    Test.prototype.findResults = function () {
      let current = this.queue.dequeue();
      while (current) {
        if (current) {
          if (getDifferenceNum(current.word, this.end) === 1
              && current.path.length <= this.deep) {
            this.deep = current.path.length;
            this.results.push(current.path);
          } else if (current.path.length < this.deep) {
            const children = this.findChildren(current);
            this.queue.enque(children);
          }
        }
    
        current = this.queue.dequeue();
      }
    };
    
    Test.prototype.filterResults = function () {
      let minLength = Number.MAX_SAFE_INTEGER;
      this.results.forEach(r => {
        if (r.length < minLength) {
          minLength = r.length;
        }
      });
      this.results = this.results.filter(r => r.length <= minLength);
    };
    
    Test.prototype.convertResults = function () {
      this.results = this.results.map(r => r.map(l => this.list[l]));
      this.results.forEach(r => r.push(this.end.join('')));
    };
    
    var findLadders = function (beginWord, endWord, wordList) {
      const tem = new Test(beginWord, endWord, wordList);
      tem.findResults();
      tem.filterResults();
      tem.list = tem.list.map(t => t.join(''));
      tem.convertResults();
      return tem.results;
    };
    

Log in to reply
 

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