126. Word Ladder II

LeetCode是用C# release模式运行的。

解法1：

使用队列进行广度优先搜索，统一在Dequeue后进行终止条件判断。

缺点是生成下一个状态，enqueue前，没有检查是不是解。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace LeetCode
{
	public class WordLadder2
	{
		public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList)
		{
			var enhancedList = wordList.Select(w => new Problem(w, GetDifferences(w, endWord))).ToList();
			var words = new List<Problem>(enhancedList);
			var transforms = FindLadders(new Problem(beginWord, GetDifferences(beginWord, endWord)), endWord,
										 words);
			//如果找不到解，按规定返回空列表
			if (transforms.Count == 0)
				return new List<IList<string>>();
			else
			{
				var result = (from t in transforms
							  select (IList<string>)t.ToList()).ToList();
				Debug.Assert(result.All(t => t[t.Count - 1] == endWord), "最后一个元素必须是endWord。");
				Debug.Assert(result.All(t => t[0] == beginWord), "第一个元素必须是beginWord。");
				return result;
			}
		}

		/// <summary>
		/// 如果beginWord等于endWord，变换长度为0。
		/// 如果beginWord无法变换到endWord，返回null。
		/// </summary>
		/// <param name="beginWord"></param>
		/// <param name="endWord"></param>
		/// <param name="wordList"></param>
		/// <returns></returns>
		List<LinkedList<string>> FindLadders(Problem beginWord, string endWord, IList<Problem> wordList)
		{
			//使用队列进行广度优先搜索
			Queue<Problem> queue = new Queue<Problem>();
			queue.Enqueue(beginWord);
			List<LinkedList<string>> shortestTransformations = new List<LinkedList<string>>();
			var wordsUsedInThisLevel = new List<Problem>();
			int currentLevel = 0; //根节点深度为0。
			while (queue.Count > 0)
			{
				var problem = queue.Dequeue();
				if (problem.UsedTransform > currentLevel) //当前层结束了，已经进入下一层
				{
					//上一层用过的词，这一次不能再用了，因为上一层某一个分支，用较少的步骤变换到了这个词，这里没必要多一个步骤变换到相同的词
					foreach (var w in wordsUsedInThisLevel)
						wordList.Remove(w);
					wordsUsedInThisLevel.Clear();
					currentLevel++;
					Debug.Assert(currentLevel == problem.UsedTransform);
				}

				if (problem.Word == endWord)
				{
					var transform = ChainTransform(problem);
					shortestTransformations.Add(transform);
				}
				else
				{
					var nextWords = from w in wordList
									where IsDifference1(w.Word, problem.Word)
									select w;
					foreach (var w in nextWords)
					{
						var p = new Problem(w.Word, w.DifferenceFromSolution, problem);
						wordsUsedInThisLevel.Add(p);
						queue.Enqueue(p);
					}
				}
			}
			return shortestTransformations;
		}

		bool IsDifference1(string w1, string w2)
		{
			Debug.Assert(w1.Length == w2.Length);

			bool hasDifference = false;
			for (int i = 0; i < w1.Length; i++)
			{
				if (w1[i] != w2[i])
				{
					if (hasDifference)
						return false;
					else
						hasDifference = true;
				}
			}

			return hasDifference;
		}

		int GetDifferences(string w1, string w2)
		{
			Debug.Assert(w1.Length == w2.Length);

			//对特殊情况进行优化
			if (w1 == w2)
				return 0;

			int hasDifference = 0;
			for (int i = 0; i < w1.Length; i++)
			{
				if (w1[i] != w2[i])
					hasDifference++;
			}

			return hasDifference;
		}

		LinkedList<string> ChainTransform(Problem p)
		{
			var list = new LinkedList<string>();
			while (p != null)
			{
				list.AddFirst(p.Word);
				p = p.Parent;
			}

			return list;
		}

		[DebuggerDisplay("Word={Word}, d={DifferenceFromSolution}")]
		class Problem: IEquatable<Problem>
		{
			public Problem(string word, int differenceFromSolution, Problem parent = null)
			{
				Word = word;
				DifferenceFromSolution = differenceFromSolution;
				Parent = parent;
				if (parent != null)
					UsedTransform = parent.UsedTransform + 1;
			}
			public string Word { get; }

			public int DifferenceFromSolution { get; }

			/// <summary>
			/// 从初始状态到达此状态已经使用的变换数量
			/// </summary>
			public int UsedTransform { get; }

			public int Heuristic => DifferenceFromSolution + UsedTransform;

			public Problem Parent { get; }

			public bool Equals(Problem other)
			{
				if (other == null)
					return false;
				return Word == other.Word;
			}

			public override bool Equals(object obj)
			{
				if (ReferenceEquals(null, obj)) return false;
				if (ReferenceEquals(this, obj)) return true;
				if (obj.GetType() != this.GetType()) return false;
				return Equals((Problem) obj);
			}

			public override int GetHashCode()
			{
				return (Word != null ? Word.GetHashCode() : 0);
			}
		}
	}
}

不需要记录solutionLevel。

List> FindLadders(Problem beginWord, string endWord, IList wordList)
{
	//使用队列进行广度优先搜索
	Queue queue = new Queue();
	queue.Enqueue(beginWord);
	List> shortestTransformations = new List>();
	var wordsUsedInThisLevel = new List();
	int currentLevel = 0; //根节点深度为0。
	//int solutionLevel = int.MaxValue;
	while (queue.Count > 0)
	{
		var problem = queue.Dequeue();

		//不需要此优化。如果solutionLevel有值，表示已经搜索过0到solutionLevel，才发现解。一旦在该层发现解，程序不会搜索solutionLevel+1层。
		//if (problem.UsedTransform > solutionLevel)
		//	continue;

		if (problem.UsedTransform > currentLevel) //当前层结束了，已经进入下一层
		{
			//上一层用过的词，这一次不能再用了，因为上一层某一个分支，用较少的步骤变换到了这个词，这里没必要多一个步骤变换到相同的词
			foreach (var w in wordsUsedInThisLevel)
				wordList.Remove(w);
			wordsUsedInThisLevel.Clear();
			currentLevel++;
			Debug.Assert(currentLevel == problem.UsedTransform);
		}

		if (problem.Word == endWord)
		{
			var transform = ChainTransform(problem);
			shortestTransformations.Add(transform);
			//solutionLevel = problem.UsedTransform;
		}
		else
		{
			var nextWords = from w in wordList
							where IsDifference1(w.Word, problem.Word)
							select w;
			foreach (var w in nextWords)
			{
				var p = new Problem(w.Word, w.DifferenceFromSolution, problem);
				wordsUsedInThisLevel.Add(p);
				queue.Enqueue(p);
			}
		}
	}
	return shortestTransformations;
}