The key to get rid of TLE.


  • 1

    The basic idea is BFS+DFS, but it is very easy to get TLE. Since we did word ladder before, then we can reuse the function to get the minimum length of the ladder. But only knowing the minimum length is not enough. If you are still doing like below in your DFS function, you get TLE. ;)

    for(String s: StringSet) {
                for(int i=0;i<length;i++) {
                    char[] cur = s.toCharArray();
                    for(char c = 'a'; c<='z'; c++) {
                        ....
                    }
                }
            }
    

    Since we already searched the neighboring letters in BFS, we can save them for our benefit. If your BFS is one-end, well, you would get TLE probably. If your BFS is two-ends, you would meet the direction issue, since you changed the position of the two sets and processed the one with smaller size. you know what I am talking about, dont you?

    So the point is that only save necessary neighboring letters and you will get a algorithm running within 100 ms.

    GLHF.


Log in to reply
 

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