word ladder

word ladder

Search again

I have done a lot of stupid things of this problem. First, I using O(n*n) time complexity to build the map and I got TLE. After I try a lot to make my searching algorithm faster and faster. Afther a lot times try, I found it is the map building already TLE....

Do not need to build the map, while searching, try to change each char of the current string. If the new string is in the set, search the new string. Because there may be cycles in the "map", and we only need the minnum steps, so the first we reach a point just delete the string from the map. The time to erase the string my affact the time. First time, I erase the string when popout, I got TLE. Then I change it to when I push it into the quee, I got AC.

 1 class Solution {
 2 public:
 3     int ladderLength(string start, string end, unordered_set<string> &dict) {
 4         queue< pair< string, int > > Q;
 5         while ( !Q.empty() ) {
 6             Q.pop();
 7         }
 8         dict.insert(end);
 9         pair< string, int > p(start,1);
10         Q.push(p);
11         while ( !Q.empty() ) {
12             auto t = Q.front();
13             Q.pop();
14             string str = t.first;
15             int step = t.second;
16             if ( str == end ) {
17                 return step;
18             }
19             int l = str.length();
20             for ( int i = 0; i < l; i++ ) {
21                 char x = str[i];
22                 for ( char j = 'a'; j <= 'z'; j++ ) {
23                     if ( x != j ) {
24                         str[i] = j;
25                         if ( dict.count(str) > 0 ) {
26                             pair< string, int > p(str,step+1);
27                             Q.push(p);
28                             dict.erase(str);
29                         }
30                         str[i] = x;
31                     }
32                 }
33             }
34         }
35         return 0;
36     }
37 };

Loading Disqus comments...
Table of Contents