Given two words and a dictionary's word list, find all shortest transformation sequence

Question

This is a leetcode problem (https://leetcode.com/problems/word-ladder-ii/description/)

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example,

Given:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Below is my code which is accepted. But I feel my algorithm is not efficient. Can you please provide recommendation on how to improve both the algorithm and the coding style?

public class Node
{
    public string Value { get; set; }
    public List<Node> Neighbors { get; set; }
    public List<Node> ShortestPathChildren { get; set; }

    public bool isVisited { get; set; }
    public int Distance { get; set; }
    public Node ()
    {
        Neighbors = new List<Node>();
        ShortestPathChildren = new List<Node>();
        Distance = int.MaxValue;
        isVisited = false;
    }

}

public class Solution
{

    public bool WithinSingleEditDistance (string s1, string s2)
    {
        int misMatchCount = 0;

        for (int i=0; i<s1.Length; ++i)
        {                
            if (s1[i] != s2[i])
            {
                if (misMatchCount > 0)
                    return false;
                else
                    misMatchCount++;
            }           
        }

        return (misMatchCount == 1);
    }
    public List<Node> BuildGraph (IList<string> wordList, string beginWord)
    {
        var graph = new List<Node>();

        if (!wordList.Contains(beginWord))
            graph.Add(new Node() { Value = beginWord });

        foreach (var word in wordList)
        {
            var node = new Node()
            {
                Value = word
            };
            graph.Add(node);
        }

        foreach (var n1 in graph)
        {
            foreach (var n2 in graph)
            {
                if (WithinSingleEditDistance(n1.Value, n2.Value))
                {
                    n1.Neighbors.Add(n2);                      
                }
            }
        }

        return graph;
    }

    public IList<IList<string>> FindLadders(
        string beginWord, string endWord, IList<string> wordList)
    {
        var graph = BuildGraph(wordList, beginWord);

        var startNode = graph.Single(x => x.Value.Equals(beginWord));

        var destNode = graph.SingleOrDefault(x => x.Value.Equals(endWord));

        if (destNode == null)
            return new List<IList<string>>();

        findPathsBFS(startNode, destNode);
        ladders = new List<IList<string>>();

        traverseDFS(startNode, destNode, new List<string>());

        return ladders;
    }

    public List<IList<string>> ladders { get; set; }
    public int MinDistance { get; set; }
    public void findPathsBFS (Node start, Node dest)
    {
        MinDistance = int.MaxValue;
        var list = new List<Node>();
        start.Distance = 0;
        list.Add(start);

        while (list.Count > 0)
        {
            var new_list = new List<Node>();

            foreach (var node in list)
            {
                if (node.Value.Equals(dest.Value))
                {
                    MinDistance = node.Distance;
                    continue;
                }

                foreach (var neighbor in node.Neighbors)
                {
                    var new_distance = node.Distance + 1;

                    if ((!node.isVisited) &&
                        (new_distance <= neighbor.Distance) &&
                        (new_distance <= MinDistance))
                    {
                        node.ShortestPathChildren.Add(neighbor);
                        neighbor.Distance = new_distance;
                        new_list.Add(neighbor);
                    }
                }

                node.isVisited = true;
            }

            list = new_list;     
        }

    }
    public void traverseDFS(Node current, Node dest, List<string> ladder )
    {
        ladder.Add(current.Value);

        if (current.Value.Equals(dest.Value))
        {
            var copied_ladder = new List<string>();
            foreach (var word in ladder)
                copied_ladder.Add(word);
            ladders.Add(copied_ladder);
            ladder.Remove(current.Value);
            return;
        }

        foreach (var child in current.ShortestPathChildren)
        {
            traverseDFS(child, dest, ladder);
        }

        ladder.Remove(current.Value);
    }
}

Answer 1

The answer from Maxim is quite good. I would emphasize a few points and add some more.

• The basic idea -- build a graph, do a traversal of the graph to extract the set of shortest paths between two nodes -- is sound.
• The separation of concerns is non-existent in this program. A node knows whether it has been visited, a node maintains details about shortest paths, a node knows its distance to something. This is a mess. It means you cannot build the graph once and then search it twice! Your code will be much, much cleaner if you separate the concerns. Build a data structure called Graph that knows how to do one, and only one thing: maintain a graph. Then build separate data structures that read but do not modify graphs.
• The algorithm can be more efficient. Suppose we are on ABCD and trying to get to WXYZ. If our choices for next steps are GBCD, HBCD and WBCD then it makes sense to explore the WBCD branch first. Possibly going to WBCD doesn't get you there at all, but if you're trying to get from start to finish and you have a choice, walking in the direction that is towards the finish line is, absent other information, the best bet.

What you can do is give each word in the graph a "score", which is "if this word is on the shortest possible path in any graph to the goal, how long is that path?" If GBCD is on the shortest possible path then that path needs to be at least four long, but WBCD could get there in three.

This gives you a "distance heuristic" which never overestimates. Now, what do you know about searching a graph when you have a distance heuristic that never overestimates?

Answer 2

Node

Properties should always have PascalCased names. So isVisited have to be changed to IsVisited.

You don't need to initialize properties in constructor. Starting with C# 6 you can initialize them in declaring statemenet:

public List<Node> Neighbors { get; } = new List<Node>();
public List<Node> ShortestPathChildren { get; } = new List<Node>();

public bool IsVisited { get; set; } = false;
public int Distance { get; set; } = int.MaxValue;

Also as you can see you can (and should) define Neighbors and ShortestPathChildren properties as readonly removing setters.

You always create a new instance of the Node specifying the Value. If this property must be set on creation of the Node add it as a parameter to the constructor:

public Node(string value)
{
    Value = value;
}

and then create nodes like this:

new Node(word);

Solution

Methods should have PascalCased names as well so findPathsBFS and traverseDFS have to be changed to FindPathsBFS and TraverseDFS respectively.

WithinSingleEditDistance

You can simplify a bit your loop:

for (int i = 0; i < s1.Length && misMatchCount < 2; ++i)
{                
    if (s1[i] != s2[i])
    {
        misMatchCount++;
    }           
}

BuildGraph

First foreach can be simplified to:

graph.AddRange(wordList.Select(w => new Node(w)));

Second foreach can be simplified to:

foreach (var n1 in graph)
{
    n1.Neighbors.AddRange(graph.Where(n2 => WithinSingleEditDistance(n1.Value, n2.Value)));
}

FindLadders

In this method you have serious architectural problem in my opinion – you initialize ladders here, then it is populated somewhere and return it. It is make your program flow unobvious and error-prone.

You should completely remove ladders field. The TraverseDFS method should return those ladders. Also I suggest to change return type of the method to IEnumerable<IList<string>>:

public IEnumerable<IList<string>> FindLadders(
    string beginWord, string endWord, IList<string> wordList)
{
    // ...

    if (destNode == null)
        return Enumerable.Empty<IList<string>>();

    FindPathsBFS(startNode, destNode);

    return TraverseDFS(startNode, destNode, new List<string>());
}

TraverseDFS

And this method should be changed to:

public IEnumerable<IList<string>> TraverseDFS(Node current, Node dest, List<string> ladder)
{
    ladder.Add(current.Value);

    if (current.Value.Equals(dest.Value))
    {
        // You don't need foreach to copy elements
        var copiedLadder = ladder.ToList();

        // Return new ladder instead of using side effects populating
        // the field
        yield return copiedLadder;

        ladder.Remove(current.Value);
        yield break;
    }

    foreach (var child in current.ShortestPathChildren)
    {
        foreach (var childLadder in TraverseDFS(child, dest, ladder))
        {
            yield return childLadder;
        }
    }

    ladder.Remove(current.Value);
}

Also local variables shouldn't use underscores. Use camelCase to name them. So use copiedLadder insetad of copied_ladder.

And I suppose this method should be private.

FindPathsBFS

new_list and new_distance should be changed to newList and newDistance.

You use MinDistance only in this method so this field have to be removed and turned to just local variable of the method. If the purpose of this method to calculate min distance then rename it. Your code suffers from side effects. Calling some method shouldn't mean setting a lot of external properties.