A C# BFS+DFS Solution


  • 0
    L
    public static List<IList<string>> findLadders(string start, string end, HashSet<string> dict)
    {
        //<string, List> contaion all the adjacent words that is discover in its previous level
        Dictionary<string, List<string>> newDict = new Dictionary<string, List<string>>();
        Queue<string> queue = new Queue<string>();                              //Queue for BFS
        ISet<string> visitedDict = new HashSet<string>();                       //Check words visited during same level
        List<IList<string>> result = new List<IList<string>>();                 //Results
        int currLen = 0, currLevCount = 1, nextLevCount = 0;
        bool found = false;
    
        dict.Add(end);
        dict.Remove(start);
        foreach (string word in dict)
            newDict.Add(word, new List<string>());
    
        //BFS
        queue.Enqueue(start);
        while (queue.Count != 0)
        {
            string currLadder = queue.Dequeue();
            //for all dict words that are one character change from current word
            foreach (string nextLadder in getNextLadders(currLadder, dict))
            {
                if (visitedDict.Add(nextLadder))
                {
                    nextLevCount++;
                    queue.Enqueue(nextLadder);
                }
                newDict[nextLadder].Add(currLadder);
                if (nextLadder.Equals(end) && !found)
                {
                    found = true;
                    currLen += 2;
                }
            }
    
            if (--currLevCount == 0)
            {
                if (found) break;
                dict.ExceptWith(visitedDict);
                visitedDict.Clear();
                currLevCount = nextLevCount;
                nextLevCount = 0;
                currLen++;
            }
        }
    
        if (found)
        {
            LinkedList<string> p = new LinkedList<string>();
            p.AddFirst(end);
            getLadders(start, end, p, result, newDict, currLen);
        }
    
        return result;
    }
    
    //get all dict words that are one character change from current word
    private static List<string> getNextLadders(string currLadder, ISet<string> dict)
    {
        List<string> nextLadders = new List<string>();
        StringBuilder replace = new StringBuilder(currLadder);
        for (int i = 0; i < currLadder.Length; i++)
        {
            char old = replace[i];
            for (replace[i] = 'a'; replace[i] <= 'z'; replace[i]++)
                if (replace[i] != currLadder[i] && dict.Contains(replace.ToString()))
                    nextLadders.Add(replace.ToString());
            replace[i] = old;
        }
        return nextLadders;
    }
    
    // DFS to get all possible path from start to end
    private static void getLadders(string start, string currLadder, LinkedList<string> p, IList<IList<string>> result, Dictionary<String, List<string>> newDict, int len)
    {
        if (currLadder.Equals(start))
            result.Add(new List<string>(p));
        else if (len > 0)
            foreach (string lad in newDict[currLadder])
            {
                p.AddFirst(lad);
                getLadders(start, lad, p, result, newDict, len - 1);
                p.RemoveFirst();
            }
    }

Log in to reply
 

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