词语序列

//主要思想：广度优先搜索。先构造一个字符串队列，并将start加入队列。1.对队列头字符串做单个字符替换
//每次替换后，2.判断是否和end匹配，如果匹配，返回答案；3.没有匹配，则在字典里面查询是否有“邻居字符串”,
//如果有，则将该字符串加入队列，同时将该字符串从字典里删除。重复1的过程，知道和end匹配。如果最后队列
//为空还未匹配到，则返回0.
   int ladderLength(string start, string end, unordered_set<string>&dict)
{
	queue<string>Q;
	Q.push(start);
	int res = 1;
	while (!Q.empty())
	{
		int qsize = Q.size(); //层次遍历，记录当前队列大小
		while (qsize--)
		{
			string cur_front = Q.front();
			Q.pop();
			int size = cur_front.size();
			for (int i = 0; i < size; i++)
			{
				char ch = cur_front[i];  //对队列头字符串每一个字符进行替换
				for (int j = 0; j < 26; j++)
				{
					cur_front[i] = 'a' + j;//替换字符
					if (cur_front == end)return res+1;//找到答案，退出
					if (dict.find(cur_front) != dict.end())
					{
						Q.push(cur_front);//变换在字典中找到了
						dict.erase(cur_front);//从字典中删除
					}
				}
				cur_front[i] = ch;//还原队列头字符串，因为有可能在字典中可以找到多个“近邻字符串”
			}
		}
		res++;//遍历一层，res+1
	}
       return 0;
}

//使用bfs(广度优先搜素)，其中res用于记录结果，size用于记录每一层的元素个数，遍历完一层res++
//注意遍历过的要从字典中删除。

public int ladderLength(String start, String end, HashSet<String> dict) {  
      int res=1;
      LinkedList<String> queue=new LinkedList<>();
      queue.offer(start);
      while(!queue.isEmpty())
      {
    	  int size=queue.size();
    	  while(size>0)
    	  {
    		  String s=queue.poll();
    		  size--;
    		  
    		  if(isDiffOne(s, end))
    			  return res+1;
    		  for(Iterator<String> it=dict.iterator();it.hasNext();)
    		  {
    			  String str=it.next();
    			  if(isDiffOne(str, s))
    			  {
    				  queue.offer(str);
    				  it.remove();
    			  }
    				  
    		  }
    	  }
    	  res++;
      }
      return 0;
    }  
  
    public boolean isDiffOne(String w1, String w2) {  
       int count = 0;          
       for(int i = 0; i < w1.length(); i++) {  
           if(w1.charAt(i) != w2.charAt(i)) {  
               count++;  
           }  
       }
       return count==1?true:false;
    }

class Solution {
public:
    int  ladderLength(string start,string end,unordered_set<string> &dict){
         dict.insert(end);
         dict.erase(start);
         queue<string> q;
         q.push(start);
         int length=0;
         while(q.size()>0)
         {    
             length++;
             int QueueLength=q.size();
             for(int i=0;i<QueueLength;i++)
                {  
                  start=q.front();
                  q.pop();
                  if(start==end) return length;
                  vector<string> deleteList;
                  for(unordered_set<string >::iterator iter=dict.begin();iter!=dict.end();iter++)
                   {  
                     int dis=distance(start,*iter);
                     if(dis==1)
                       {
                        q.push(*iter);
                        deleteList.push_back(*iter);
                       }
                    }
                  for(int i=0;i<deleteList.size();i++)
                        dict.erase(deleteList[i]);
                  }
          }
        return 0;
    }
    int distance(string s1,string s2)
    {
        int count=0;
        for(int i=0;i<s1.size();i++)
        {
            if(s1[i]!=s2[i]) count++;
            
        }
        return count;
        
        
    }
};

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
      int res=1;
      queue<string> que;
      unordered_set<string>::iterator it;
      que.push(start);
      while(!que.empty())
      {
          int size=que.size();
          while(size--)
          {
              string s=que.front();
              que.pop();
               
              if(IsSuit(s, end))
                  return res+1;
              for(it=dict.begin();it!=dict.end();)
              {
                  string str=*it;
                  if(IsSuit(s,str))
                  {
                      que.push(str);
                      it=dict.erase(it);
                  }
                  else
                      ++it;
              }
          }
          res++;
      }
      return 0;
    } 
    
    bool IsSuit(string &s,string &str)
    {
        int num=s.length();
        int a=0;
        for(int i=0;i<num;++i)
        {
            if(s[i]!=str[i])
                ++a;
            if(a>1)
                return false;
        }
        if(a==1)
            return true;
        return false;
    }
};

    int ladderLength(string start, string end, unordered_set<string> &dict) {
        queue<string> q1,q2,*p1,*p2;
        int count=0;
        for(p1=&q1,p2=&q2,p1->push(start);p1->size();swap(p1,p2)){
            ++count;
            for(string str;p1->size();p1->pop()){
                str = p1->front();           
            	for(int i=0;i<str.length();++i){
                	string s=str;
                    for(char ch='a';ch<='z';++ch){
                        if (ch==str[i]) continue;
                        s[i] = ch;
                        if (s==end) return count+1;
                        if (dict.find(s)!=dict.end()){
                            p2->push(s);
                            dict.erase(s);    // 防止死循环（回路）
                        }
                    }
                }
            }
        }
        return 0;
    }

class Solution {
public:
  int ladderLength(string start, string end, unordered_set<string> &dict) {
    if (!dict.count(end)) return 0;

    queue<string> q{{start}};
    unordered_set<string> seen{start};

    int steps = 0;
    while (not q.empty()) {
      size_t s = q.size();
      while (s--) {
        const auto curr = q.front(); q.pop();
        if (curr == end) return steps + 1;
        for (int i = 0; i < curr.length(); ++i) {
          string nxt(curr);
          const char c = curr[i];
          for (char j = 'a'; j <= 'z'; ++j) {
            if (j == c) continue;
            nxt[i] = j; 
            if (seen.count(nxt) || !dict.count(nxt)) continue;
            q.emplace(nxt);
            seen.emplace(nxt);
          }
        }
      }
      ++steps;
    }

    return 0;
  }
};

import java.util.*;
public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        int wordSize = start.length(), level = 1;
        Queue<ArrayList<String>> paths = new LinkedList<ArrayList<String>>();
        paths.offer(new ArrayList<String>() {{
            add(start);
        }});
        ArrayList<String> words = new ArrayList<String>();
        words.add(start);
        while(!paths.isEmpty()){
            ArrayList<String> path = paths.poll();
            int currentSize = path.size();
            if(currentSize > level){
                for(String str : words){
                    dict.remove(str);
                }
                words.clear();
                level = currentSize;
            }

            String lastWord = path.get(currentSize - 1);
            for(int i = 0; i < wordSize; i++){
                for(char c = 'z'; c >= 'a'; c--){
                    char[] charArr = lastWord.toCharArray();
                    charArr[i] = c;
                    String newWord = new String(charArr);
                    if(newWord.equals(end)){
                        return currentSize + 1;
                    }else if(dict.contains(newWord)){
                        words.add(newWord);
                        paths.offer(deepCopy(path, newWord));
                    }
                }
            }
        }
        return 0;
    }
    static ArrayList<String> deepCopy(ArrayList<String> arr, String newWord){
        ArrayList<String> newPath = new ArrayList<String>();
        for(String str : arr){
            newPath.add(str);
        }
        newPath.add(newWord);
        return newPath;
    }
}

BFS,用last和nlast变量标记是否换层
int ladderLength(string start, string end, unordered_set<string> &dict) {
        deque<string> que;
        que.push_back(start);
        int level=1;
        string last=start;
        string nlast="";
        while(!que.empty()){
            string s=que.front();
            que.pop_front();
            //逐个变s
            for(int i=0;i<s.length();i++){
                char tmp=s[i];
                for(int j=0;j<26;j++){
                    s[i]='a'+j;
                    //变换得到end
                    if(s==end){
                        return level+1;
                    }
                    if(dict.find(s)!=dict.end()){
                        que.push_back(s);
                        dict.erase(s);
                        nlast=s;
                    }
                }
                s[i]=tmp;
            }
            if(s==last){
                level++;
                last=nlast;
            }
        }
        return 0;
    }

class Solution {
public:
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        queue<string> q1,q2,*p1,*p2;
        int count = 0;
        p1 = &q1;         p2 = &q2;          for(p1->push(start);!p1->empty();swap(p1,p2))         {             count++;             for(;!p1->empty();p1->pop())             {                 string s = p1->front();                 for(int i=0;i<s.length();i++)                 {                     string t = s;                     for(char c='a';c<='z';c++)                     {                         if(c==s[i])                             continue;                         t[i] = c;                         if(t==end)                             return count+1;                         if(dict.find(t) != dict.end())                         {                             p2->push(t);                             dict.erase(t);                         }                     }                 }             }         }
        return 0;
    }
};

//有没有大佬解释一下为什么我用注释里的构造next的方***报超时，
//改成转数组的方式就直接AC了？先谢过了
import java.util.*;

public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
		
        Queue<String> que = new LinkedList<String> ();
        HashSet<String> visited = new HashSet<String> ();
        Queue<Integer> num = new LinkedList<Integer> ();

        que.add(start);
        num.add(1);
        visited.add(start);
        
        while(!que.isEmpty()){
            String str = que.remove();
            int nums = num.remove();
            if(str.equals(end))
                return nums;
            for(int i = 0; i < start.length(); ++i){
                char [] arr = str.toCharArray();
                for(char c = 'a'; c <= 'z'; ++c){
                    arr[i] = c;
                    String next = new String(arr);
                    //String next = str.substring(0,i) + c + str.substring(i+1,start.length());
                    if(dict.contains(next) && !visited.contains(next)){
                        que.add(next);
                        num.add(nums+1);
                        visited.add(next);
                    }
                }
            }
        }
        
        return 0;
    }
}

package go.jacob.day0530.queue;

import java.util.*;

/**
 * 解法：
 * 该题一样可以简化为图论的问题
 */
public class P127_WordLadder {

    public static int ladderLength(String beginWord, String endWord, HashSet<String> dict) {
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.offer(new Pair(beginWord, 1));
        Set<String> visited = new HashSet<String>();

        if (!dict.contains(endWord))
            return 0;

        while (!queue.isEmpty()) {
            String str = queue.peek().str;
            int step = queue.peek().step;
            queue.poll();

            for (int i = 0; i < str.length(); i++) {
                char[] chars = str.toCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;

                    String word = new String(chars);
                    if (word.equals(endWord))
                        return step + 1;

                    if (dict.contains(word) && !visited.contains(word)) {
                        queue.add(new Pair(word, step + 1));
                        visited.add(word);
                    }
                }
            }
        }

        return 0;
    }

    static class Pair {
        public String str;
        public int step;

        public Pair(String str, int step) {
            this.str = str;
            this.step = step;
        }
    }


}

import java.util.*;

public class Solution
{
    public int ladderLength(String start, String end, HashSet<String> dict)
    {
        if(start == null || end == null || start.length() == 0 || end.length() == 0)
            return 0 ;

        dict.remove(start) ;
        dict.remove(end) ;

        if(isDifferOne(start , end))
            return 2 ;

        int l = bfs(start , end , dict) ;
        return l < 0 ? 0 : l+1 ;
    }

    private int bfs(String start , String end , HashSet<String> dict)
    {
        Iterator<String> it = dict.iterator() ;
        Queue<String> queue = new LinkedList<>() ;

        while (it.hasNext())
        {
            String str = it.next() ;
            if(isDifferOne(start , str))
            {
                queue.add(str) ;
                it.remove() ;
            }
        }

        int l = bfs(queue , end , dict) ;
        return l < 0 ? -1 : l+1 ;
    }

    private int bfs(Queue<String> queue , String end , HashSet<String> dict)
    {
        int size = queue.size() ;

        for(int i=0 ; i<size ; i++)
        {
            Iterator<String> it = dict.iterator() ;
            String str = queue.poll() ;
            if(isDifferOne(str , end))
                return 1 ;

            while (it.hasNext())
            {
                String next = it.next() ;
                if(isDifferOne(str , next))
                {
                    queue.add(next) ;
                    it.remove() ;
                }
            }
        }

        if(queue.size() == 0)
            return -1 ;

        int l = bfs(queue , end , dict) ;

        return l<0 ? -1 : l+1 ;
    }

    private boolean isDifferOne(String s1 , String s2)
    {
        int differ = 0 ;
        for(int i=0 ; i<s1.length() ; i++)
        {
            if(s1.charAt(i) != s2.charAt(i))
                differ++ ;
            if(differ > 1)
                return false ;
        }

        return true ;
    }
}

解题思路 :

将两个串之间的最短距离问题转化为图中节点的最短距离，运用迪杰斯特拉算法进行BFS .

    }

import java.util.*;
public class Solution {
    public int ladderLength(String beginWord, String endWord, HashSet<String> set) {
        int depth = 1;
        Queue<String> queue = new LinkedList(); 
        queue.offer(beginWord);
        int cnt = queue.size();
        boolean flag = false;
        while(!queue.isEmpty()){
            for(String s:queue)
                set.remove(s);
            cnt--;
            String a = queue.poll();
            if(a.equals(endWord)){
                flag = true;
                break;
            }
            for(String str:set){
                 if(distance(a,str)){
                     queue.offer(str);
                 }
            }
            if(cnt==0){
                cnt = queue.size();
                depth++;
            }
        }
        if(flag)
            return depth;
        else
            return 0;
    }
    private boolean distance(String a,String b){
        int cnt = 0;
        if(a.length()!=b.length())
            return false;
        for(int i=0;i<a.length();i++){
            if(a.charAt(i)!=b.charAt(i))
                cnt++;
        }
        return cnt==1?true:false;
    }
}

没做过这种图论的题目，一脸懵逼😳，看了大佬的解析，自己再总结（fushu）一遍：

将所有路径表示出来——

        ->lot->log
hit->hot          ->cog
        ->dot->dog

这个其实就是求图论中的单源最短路径，图中边是没有权重的，用BFS求解最合适（时间复杂度O(n)）。

class Solution {
public:
    int ladderLength(string start, string end, unordered_set &dict) {
        queue> record;
        record.push(make_pair(start, 1));
        while (!record.empty()) {
            pair current = record.front();
            record.pop();
            if (current.first == end) {
                return current.second;
            }
            // 替换每一个字符，并在set中搜寻
            for (int i = 0; i < current.first.size(); ++i) {
                for (int j = 0; j < 26; ++j) {
                    string str = current.first;
                    str[i] = 'a' + j;
                    if (dict.find(str) != dict.end()) {
                        record.push(make_pair(str, current.second+1));
                        dict.erase(str);
                    }
                }
            }
        }
        return 0;
    }
};

class Solution{
    /*
	双向bfs并不是从两端同时bfs, 实际上是这次从begin进行bfs, 下次从end进行bfs, 像这样循环操作
	*/
	private static int ladderLength(String beginWord, String endWord, HashSet<String> dict) {
		//endWord也是transformed word, 所以必须存在于wordList中, 否则返回0, 表示无法从beginWord变成endWord
		if(!dict.contains(endWord))
			return 0;
		//每个单词长度相同
		int n = beginWord.length();
		//key是通用状态; value是拥有该通用状态的词
		HashMap<String, ArrayList<String>> allcommons = new HashMap<>();
		//记录wordList中所有元素对应的所有通用状态
        //curword当前正在遍历的单词
		for(String curword:dict) {
			for(int i=0; i<n; i++) {//每个单词都能得到n种通配词，每个位置都可变为*
				String common = curword.substring(0,i)+"*"+curword.substring(i+1);
				if(!allcommons.containsKey(common))
					allcommons.put(common, new ArrayList<>());
				allcommons.get(common).add(curword);
			}
		}
		//使用HashSet实现宽度优先遍历bfs
		HashSet<String> begin = new HashSet<>();
		HashSet<String> end = new HashSet<>();
		begin.add(beginWord);
		end.add(endWord);
		//记录访问过的节点
		HashSet<String> visited = new HashSet<>();
		//返回值的初始化, 由于beginWord!=endWord, 所以至少需要一步变化
		int len = 1;
		while(!begin.isEmpty()&&!end.isEmpty()) {
			//记录遍历begin时每个元素的邻居, 也就是cur的邻居
			HashSet<String> neighbor = new HashSet<>();
			for(String cur:begin) {//遍历cur的邻居
				for(int i=0; i<n; i++) {
					//有了all_commons哈希表,就不用每个位置都遍历'a'~'z'了
                    //细节:如果cur是beginWord的话, all_commons没有统计beginWord的通用状态,
					//所以all_commons.get(tmp)可能返回null, 所以要提前检查一下
					String tmp = cur.substring(0,i)+"*"+cur.substring(i+1);
					if(!allcommons.containsKey(tmp))
						continue;
					for(String str:allcommons.get(tmp)) {
						if(end.contains(str))
							return len+1;
						if(!visited.contains(str)) {
							visited.add(str);
							//记录cur的邻居
							neighbor.add(str);
						}
					}
				}
			}
			//处理完begin中的元素后, 让begin指向begin中的元素的邻居
			begin = neighbor;
			len++;
		}
		//执行到这里说明双向bfs没有相遇, 也就是没有找到从beginWord到endWord的路径
		return 0;
	}
	
}
}

有点难理解