C++ use bfs have a clear mind


  • 0
    R
    • use bfs
    • attention the ret++ location
    class Solution_127 {
    public:
    	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    		string start = beginWord;
    		string end = endWord;
    		unordered_set<string> dict(wordList.begin(), wordList.end());
    
    		if (start == end || dict.empty())
    		{
    			return 0;
    		}
    		int ret = 1;
    
    		queue<string> que; //bfs
    		que.push(start);
    		while (!que.empty())
    		{
    			int size = que.size();  //层次遍历,记录当前队列大小
    
    			while (size--)  //不加这层循环,ret++是对每次元素出队列就计数;加循环就是严格每层计数++
    			{
    				string temp = que.front();
    				que.pop();
    				for (int i = 0; i < temp.size(); i++)
    				{
    					char ch = temp[i]; //对每个单词的每次字符替换构成新的单词,查看是否在字典中
    
    					for (int j = 0; j < 26; j++) //对同一个单词处理,ret++不应该放在里面
    					{
    						temp[i] = 'a' + j; //替换
    						if (dict.find(temp) != dict.end()) //找到了  需要吗?&&temp[i]!=ch不影响答案
    						{
    							//ret++; //找到一个计数+1 
    							if (temp == end)
    							{
    								return ret + 1;  //找到答案,退出
    							}
    							que.push(temp);
    							dict.erase(temp);
    						}
    					}
    					temp[i] = ch; //还原单词
    				}
    			}
    			ret++;
    		}
    
    		return 0;
    	}
    };
    

  • 0
    S

    26? Consider this:

    for (int tmp[i] = 'a'; tmp[i] <= 'z'; tmp[i]++) {
      if (tmp[i] != ch && dict.find(temp) != dict.end())
    

    Other than that it is very readable solution.


Log in to reply
 

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