About Teletype
Join
Oleg
@olegtar
September 23

Разбор задачи 126. Word Ladder II с Литкода. Pretty Hard

https://leetcode.com/problems/word-ladder-ii/

Условие

Последовательность трансформации от слова beginWord до слова endWord с использованием словаряwordList это последовательность слов beginWord -> s1 -> s2 -> ... -> sk такая что:

  • Каждая соседняя пара слов отличается одной буквой.
  • Каждый si для 1 <= i <= k есть в wordList. ЗаметьеbeginWord необязательно будет вwordList.
  • sk == endWord

Дано два слова: beginWord иendWord, и словарь wordList, верните все самые короткие последовательности трансформации от beginWord доendWord, или пустой список если такая последовательность не существует. Каждая последовательность должна быть возвращена как лист слов [beginWord, s1, s2, ..., sk].

Пример 1:

Ввод: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Вывод: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Объяснение: Здесь 2 самых коротких последовательностей трансформации:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Пример 2:

Ввод: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Вывод: []
Объяснение: Слово "cog" не в wordList, поэтому здесь нет валидной последовательности трансформации.

Ограничения:

  • 1 <= beginWord.length <= 5
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 500
  • wordList[i].length == beginWord.length
  • beginWord, endWord, иwordList[i] состоят из маленьких английских букв.
  • beginWord != endWord
  • Все слова в wordList уникальны.
  • Сумма все самых коротких последовательностей трансформации не превышает 10^5.

Решение

Код который, который нужно дополнить выглядит вот так:

public Solution
{
  public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) 
  {
  }
}

нам нужно вернуть IList<IList<string>> (лист листов)
beginWord может содержаться, а может и нет в wordList, поэтому подготовим список всех уникальных слов из wordList включая слово beginWord.

var set = new HashSet<string>(wordList);
set.Add(beginWord);

Проверим, что если конечное слово не содержится в общем списке, то мы сразу выходим.

if (!set.Contains(endWord))
{
	return [];
}

Чтобы найти кратчайший путь от слова А, до слова Б, построим граф, где узел будет слово. Нам надо найти кратчайший путь от А до Б, при этом помним, что по условию задачи соседние слова должны отличаться только на один символ.

Заведем узел для графа.

public class Node    
{        
   public string Word {get; set;} = null;        
   public List<Node> Neighbors {get; set;} = [];        
}

Word - это слово
List<Node> Neighbors - это список всех соседей узла.
Так как в последовательности трансформации два соседних слова должны отличаться только на один символ, то это значит, что слова соседей одного узла должны отличаться от слова этого узла только одним символом.

Создадим вспомогательную функцию, которая возвращает true, если слова отличаются только одним символом, иначе - false.

public bool IsDiffOnlyByOneChar(string word1, string word2)
{ 
    var countDiff = 0;
    for (var i = 0; i < word1.Length; i++)
    {
          if (word1[i] != word2[i])
          {
            countDiff++;
            if (countDiff > 1)
            {
              return false;
            }
       }
    }
    return countDiff == 1;
}

Построим граф, где соседними узлами какого-то узла будут узлы со словом, отличающимся только на один символ от слова этого узла.

Но один узел может быть соседом сразу нескольких узлов, поэтому будем запоминать уже созданные узлы в словаре map:
var map = new Dictionary<string, Node>();

где ключ слово, а value - узел, его содержащий. И так, построим граф:

var map = new Dictionary<string, Node>();        
foreach (var word in set)
{
    Node currentNode = null;
    if (!map.TryGetValue(word, out currentNode))
    {
        map[word] = new Node()
        {
            Word = word
        };
        currentNode = map[word];
    }

    foreach (var otherWord in set)
    {
        if (IsDiffOnlyByOneChar(word, otherWord))
        {
            Node neighborNode = null;
            if (!map.TryGetValue(otherWord, out neighborNode))
            {
                map[otherWord] = new Node
                {
                    Word = otherWord
                };
                neighborNode = map[otherWord];
            }
            currentNode.Neighbors.Add(neighborNode);
        }
    }
}

Теперь нам надо стартовать от узла со словом beginWord и идти до узла со словом endWord.

Проход будет таким

Проход по графу

Каждая итерация отделена пунктирной линией.

Примерный код такой (он нерабочий):

var queue = new Queue<Node>();//очередь в которую будут класться соседи
queue.Enqueue(map[beginWord]);//кладем первый узел
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    for (var i = 0; i < cnt; i++)
    {
        //вытаскиваем первый узел на первой итерации
        //на всех последующих итерациях вытаскиваем соседей
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конечного узла
        }
        
        //проходимся по соседям
        foreach (var neighbor in node.Neighbors)
        {                    
            queue.Enqueue(nextNode);
        }                
    }
}

Но нужно решить две проблемы. Первая - надо избежать зацикливания. Ведь если узел Б сосед А, то и наоборот узел А является соседом узла Б. А также зацикливание может быть через несколько узлов.

Введем в узел свойство int Cnt.
Для первого узла и первой итерации оно будет равно нулю.
Для соседей первого узла (т.е. при второй итерации), оно будет равно 1.
Для соседей соседей первого узла (третья итерация), оно будет равно 2.
и т.д.
Итак, если узел А имеет значение Cnt == N, то сосед узла Б должен иметь значение Cnt == N + 1. Если так окажется, что у узла Б будет сосед В, который будет иметь соседа А, то при переходе от узла В к соседнему узлу (узлу А), мы должны проверить, а не установлено ли у него Cnt. Если оно установлено и уже меньше или равно чем Cnt текущего узла, то значит, если мы зайдем в этот узел, мы зациклимся.

Итак, класс Node обрастает ещё одним свойством:

public class Node    
{        
   public string Word {get; set;} = null;        
   public List<Node> Neighbors {get; set;} = [];   
   public int Cnt {get;set;} = int.MaxValue;
}

По умолчанию Cnt = int.MaxValue, чтобы можно было таким if'ом проверить, стоить ли заходить в узел или нет:
if (neighbor.Cnt <= node.Cnt)

Если условие выполняется, то значит мы уже были в neighbor, и поэтому пропускаем этот узел. По условию задачи у нас не более 501 узла (500 слов wordList и одно слово beginWord), так что Cnt не может достигнуть int.MaxValue в процессе обхода.
Итого, код обхода получается таким:

var queue = new Queue<Node>();//очередь в которую будут класться соседи
map[beginWord].Cnt = 0;
queue.Enqueue(map[beginWord]);//кладем первый узел
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    for (var i = 0; i < cnt; i++)
    {
        //вытаскиваем первый узел на первой итерации
        //на всех последующих итерациях вытаскиваем соседей
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конечного узла
        }
        
        //проходимся по соседям
        foreach (var neighbor in node.Neighbors)
        { 
            if (neighbor.Cnt <= node.Cnt)
            {
                continue;//пропускаем узел
            }
            neighbor.Cnt = node.Cnt + 1;                  
            queue.Enqueue(nextNode);
        }                
    }
}

Но есть вторая проблема, два разных узла могут ссылаться на один и тот же узел. Если ничего не сделать, то на следующей итерации мы можем достать этот узел дважды, и дважды добавить в очередь его соседей. Что в итоге может привести к багам, когда будем строить цепочки трансформации, они будут дублироваться (и приводит, я проверил :-)). Поэтому при обработке узлов в итерации всех соседей будем добавлять не сразу в очередь, а в HashSet, а потом из HashSet в очередь:

var nextNodes = new HashSet<Node>();
var queue = new Queue<Node>();//очередь в которую будут класться соседи
map[beginWord].Cnt = 0;
queue.Enqueue(map[beginWord]);//кладем первый узел
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    nextNodes.Clear();//подготавливаем set для очередных соседей
    for (var i = 0; i < cnt; i++)
    {
        //вытаскиваем первый узел на первой итерации
        //на всех последующих итерациях вытаскиваем соседей
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конечного узла
        }
        
        //проходимся по соседям
        foreach (var neighbor in node.Neighbors)
        { 
            if (neighbor.Cnt <= node.Cnt)
            {
                continue;//пропускаем узел
            }
            neighbor.Cnt = node.Cnt + 1;                  
            nextNodes.Add(neighbor);
        }                
    }
    
    //кладем очередних соседей, исключая дубликаты
    foreach (var nextNode in nextNodes)
    {    
         queue.Enqueue(nextNode);
    }
}

Окей, зацикливание исключили, проход в один и тот же узел исключили. Дошли до конечного узла, а дальше-то что? Нам надо теперь раскрутить путь от endWord до beginWord обратно. Путей может быть несколько.
Как узнать путь обратно?
Введем новое поле List<Node> Back {get; set;}, которое будет указывать на узлы из которого можно прийти в этот узел.

public class Node
{
    public string Word {get; set;} = null;
    public List<Node> Back = [];
    public List<Node> Neighbors {get; set;} = [];
    public int Cnt {get; set;} = int.MaxValue;
}

Разница между Back и Neighbors в том, что Neighbors - это соседи вообще, а Back содержит только те узлы, которые попадут в трансформацию: beginWord -> s1 -> s2 -> ... -> endWord

Итак, теперь обход такой:

var nextNodes = new HashSet<Node>();
var queue = new Queue<Node>();
map[beginWord].Cnt = 0;
queue.Enqueue(map[beginWord]);
while (queue.Count() > 0)
{
    var cnt = queue.Count();
    nextNodes.Clear();
    for (var i = 0; i < cnt; i++)
    {
        var node = queue.Dequeue();
        if (node.Word == endWord)
        {         
            //дошли до конца
        }
        
        foreach (var neighbor in node.Neighbors)
        {                    
            if (neighbor.Cnt <= node.Cnt)
            {
                continue;
            }
            neighbor.Back.Add(node);//записываем путь назад
            neighbor.Cnt = node.Cnt + 1;
            nextNodes.Add(neighbor);
        }                
    }
    foreach (var nextNode in nextNodes)
    {
        queue.Enqueue(nextNode);
    }
}

Итак, мы подходим к концовке.
У нас есть узел node c Word == endWord, у этого узла есть Back со списком узлов, которые отличаются на одну букву и которые участвуют в трансформации, и у этих узлов тоже есть свои свойства Back.

Нужно идти перебором по всем узлам списка Back, для каждого узла из этого списка идти перебором по всем узлам его списка Back, и т.д.

Заведем переменную для результата:

var result = new List<IList<string>>();

Заведем вспомогательную функцию Solve, которая собирается все пути от endWord до beginWord, переворачивает их и добавляет в результат:

//Node текущий узел (endWord -> sk -> s2 -> s1 -> beginWord)
//result результат
//текущий путь в словах List<string> path = endWord, sk, s2, s1, beginWord
public void Solve(Node node, IList<IList<string>> result, List<string> path, 
string beginWord)
{
    //дошли до конечного узла, рекурсия здесь останавливается
    if (node.Word == beginWord)
    {
        //добавили слово
        path.Add(beginWord);
        //сделаю копию. Копия нужна, так как path может быть задействован
        //где-то ещё.
        List<string> copyPath = [..path];
        //перевернули путь
        copyPath.Reverse();
        //добавили в результат
        result.Add(copyPath);
        //удалили последнее слово из результата
        //нужно для возврата назад на несколько слов
        //некоторые пути могут частично совпадать
        //endWord -> a -> b -> d
        //endword -> c -> b -> d
        path.RemoveAt(path.Count - 1);
        return;
    }
    
    //добавили очередное слово в путь
    path.Add(node.Word);
    //перебор всех последующих слов в nodeBak
    foreach (var backNode in node.Back)
    {
        Solve(backNode, result, path, beginWord);
    }
    //сделали возврат.
    path.RemoveAt(path.Count - 1);
}

Это "перебор с возвратами", по-английски - "BackTracking".

Так вот, полное решение такое:

public class Solution 
{
    public class Node
    {
        public string Word {get; set;} = null;
        public List<Node> Back = [];
        public List<Node> Neighbors {get; set;} = [];
        public int Cnt {get; set;} = int.MaxValue;
    }

    public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
        var set = new HashSet<string>(wordList);
        set.Add(beginWord);
        
        if (!set.Contains(endWord))
        {
            return [];
        }

        //строим граф
        var map = new Dictionary<string, Node>();        
        foreach (var word in set)
        {
            Node currentNode = null;
            if (!map.TryGetValue(word, out currentNode))
            {
                map[word] = new Node()
                {
                    Word = word
                };
                currentNode = map[word];
            }

            foreach (var otherWord in set)
            {
                //сосед? добавляем
                if (IsDiffOnlyByOneChar(word, otherWord))
                {
                    Node neighborNode = null;
                    if (!map.TryGetValue(otherWord, out neighborNode))
                    {
                        map[otherWord] = new Node
                        {
                            Word = otherWord
                        };
                        neighborNode = map[otherWord];
                    }
                    currentNode.Neighbors.Add(neighborNode);
                }
            }
        }
        
        //обход графа в ширину
        //чтобы не обходить соседа дважды, если он сосед двух узлво
        var nextNodes = new HashSet<Node>();
        var queue = new Queue<Node>();
        //у первого узла Cnt = 0
        map[beginWord].Cnt = 0;
        queue.Enqueue(map[beginWord]);
        var result = new List<IList<string>>();
        while (queue.Count() > 0)
        {
            //подготавливаем соседей текущих узлов для следующей итерации
            nextNodes.Clear();
            while (queue.Count() > 0)
            {
                var node = queue.Dequeue();
                //дошли до конечного узла?
                if (node.Word == endWord)
                {
                    //раскручиваем пути назад         
                    Solve(node, result, [], beginWord);
                    return result;
                }
                
                foreach (var neighbor in node.Neighbors)
                {              
                    //уже проходили этот узел?      
                    if (neighbor.Cnt <= node.Cnt)
                    {
                        continue;
                    }
                    //Путь назад
                    neighbor.Back.Add(node);
                    //Метка, чтобы не зациклиться
                    neighbor.Cnt = node.Cnt + 1;
                    nextNodes.Add(neighbor);
                }                
            }
            //подготавливаем новые узлы для следующей итерации
            foreach (var nextNode in nextNodes)
            {
                queue.Enqueue(nextNode);
            }
        }
        return [];
    }
    
    //Перебор с возвратами
    public void Solve(Node node, IList<IList<string>> result, List<string> path, string beginWord)
    {
        if (node.Word == beginWord)
        {
            path.Add(beginWord);
            List<string> copyPath = [..path];
            copyPath.Reverse();
            result.Add(copyPath);
            path.RemoveAt(path.Count - 1);
            return;
        }

        path.Add(node.Word);
        foreach (var backNode in node.Back)
        {
            Solve(backNode, result, path, beginWord);
        }
        path.RemoveAt(path.Count - 1);
    }

    public bool IsDiffOnlyByOneChar(string word1, string word2)
    {
        var countDiff = 0;
        for (var i = 0; i < word1.Length; i++)
        {
            if (word1[i] != word2[i])
            {
                countDiff++;
                if (countDiff > 1)
                {
                    return false;
                }
            }
        }
        return countDiff == 1;
    }
}
Oleg
September 23, 20:38
0 views
0 reactions
0 replies
0 reposts