赞
踩
- class Solution {
- public:
- int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
- // 单词字典,方便查询
- unordered_set<string> s(wordList.begin(), wordList.end());
- // 记录单词的出现
- unordered_map<string, int> m;
- if (!s.count(endWord))
- return 0;
- m[beginWord] = 1;
- queue<string> q;
- q.push(beginWord);
- // 层序遍历
- while(!q.empty()){
- string word = q.front();
- q.pop();
- for(int i = 0; i < word.length(); ++i){
- string tmp = word;
- for (char j = 'a'; j <= 'z'; ++j){
- tmp[i] = j;
- if (s.count(tmp)){
- if (tmp == endWord)
- return m[word] + 1;
- if (!m.count(tmp)){
- q.push(tmp);
- m[tmp] = m[word] + 1;
- }
- }
- }
- }
- }
- return 0;
- }
- };
-
- static int x=[](){
- std::ios::sync_with_stdio(false);
- cin.tie(NULL);
- return 0;
- }();
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。