127. Word Ladder

發表於 | 分類於

problem

solution

option 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        if(!words.count(endWord)) return 0;
        int depth = 1;
        queue<string> q({beginWord});
        unordered_set<string> visited;
        visited.insert(beginWord);
        while(!q.empty()){
            int size = q.size();
            for(int i=0;i<size;++i){
                string p = q.front();
                q.pop();
                if(p == endWord) return depth;
                
                int len = p.size();
                for(int j=0;j<len;++j){
                    string temp = p;
                    for(char c = 'a' ;c<='z';++c){
                        string t = temp;
                        t[j] = c;
                        if(!visited.count(t) && words.count(t)){
                            q.push(t);
                            visited.insert(t);
                        }
                    }
                }
            }
            depth++;
        }
        return 0;
        
    }
};

find() 代替count 會更快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        if(words.find(endWord) == words.end()) return 0;
        int depth = 1;
        queue<string> q({beginWord});
        unordered_set<string> visited;
        visited.insert(beginWord);
        while(!q.empty()){
            int size = q.size();
            for(int i=0;i<size;++i){
                string p = q.front();
                q.pop();
                if(p == endWord) return depth;
                int len = p.size();
                for(int j=0;j<len;++j){
                    string temp = p;
                    for(char c = 'a' ;c<='z';++c){
                        temp[j] = c;
                        if(visited.find(temp)==visited.end() && words.find(temp)!=words.end()){
                            q.push(temp);
                            visited.insert(temp);
                        }
                    }
                }
            }
            depth++;
        }
        return 0;
        
    }
};

analysis

  • time complexity O(nm)
  • space complexity O()