BSF, did some optimizations, but still get TLE in case "nanny", "aloud", ["ricky",...


  • -2
    M

    Using a queue to do a bfs search.

    My optimizations:

    1. Deleted the visited dict words.
    2. Store the transform path with a list.

    How can I get my code more,,,more faster?

    Actually I also tried to store the dict with a new adjacent dict but got MLT...

    class Solution {
    public:
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            vector<vector<string>> result;
            if(start == end || start.size() <= 0)
                return result;
    
            queue<Node*> paths;
            Node *startNode = new Node(end);  //search from end to start so we can get a start-to-end path at last using pre list
            paths.push(startNode);
            paths.push(NULL);     //level tag
            bool isReached = false;     //whether we reached the start
            while(!paths.empty()){
                Node *cur = paths.front();
                paths.pop();
                if(cur != NULL){
                    //delete visited words
                    dict.erase(cur->val);
                    //add all possible next transform words
                    for(int i = 0; i < (cur->val).size(); i++){
                        for(char c = 'a'; c <= 'z'; c++){
                            string newStr = cur->val;
                            newStr[i] = c;
                            if(newStr == start){
                                isReached = true;
                                Node *newNode = new Node(newStr);
                                newNode->pre = cur;
                                paths.push(newNode);
                                break;
                            }
                            if(dict.find(newStr) != dict.end()){
                                Node *newNode = new Node(newStr);
                                newNode->pre = cur;
                                paths.push(newNode);
                            }
                        }
                    }
                } else{
                    if(isReached || paths.empty())
                        break;
                    paths.push(NULL);
                }
            }
            //get start-to-end path
            while(!paths.empty()){
                Node *cur = paths.front();
                paths.pop();
                if(cur->val == start){
                    vector<string> path;
                    do{
                        path.push_back(cur->val);
                        cur = cur->pre;
                    }while(cur != NULL);
                    result.push_back(path);
                }
            }
            return result;
        }
    private:
        //path list
        struct Node{
            string val;
            struct Node *pre;
            Node(string val):val(val), pre(NULL){}
        };
    };

  • 0
    X
    1. Browse dict to see if the element links to current node is a little bit faster than generate a possible word from current node and check if it is in the dict. I have tried both ways to draw this conclusion.

    2. Two-directional BFS starts from both start and end is several times faster than one-directional BFS only starts from the start. To implement two-directional BFS, you have a start-tree, and an end-tree. You need to be careful that the solution may has odd nodes or even nodes which are different situations.


  • 0
    C

    Some transformations can lead you to a word that has been visited in previous iterations.

    Keep track of the distance of each transformation from the 'start' word like what you would do if you use BFS to determine the shortest path distance in a graph. Then you can use the distance to check if a transformation is lower in the word ladder so you can avoid adding them to the BFS queue.


  • 0
    W

    Two-directional BFS starts from both start and end is several times faster than one-directional BFS only starts from the start - only when there is a path from start to end. If no, you will search two entire trees.


Log in to reply
 

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