Алгоритм для преобразования одного слова в другое через правильные слова

Я столкнулся с этим вариантом проблемы редактирования на расстоянии :

Разработайте алгоритм, который преобразует исходное слово в целевое слово. например: от головы до хвоста, на каждом шаге вы можете просто заменить один символ, и слово должно быть допустимым. Вам будет предоставлен словарь.

Это, очевидно, вариация расстояния редактирования проблема, но на расстоянии редактирования меня не волнует, является ли слово действительным или нет. Итак, как мне добавить это требование для редактирования расстояния.

38 голосов | спросил gameover 5 FebruaryEurope/MoscowbFri, 05 Feb 2010 10:02:55 +0300000000amFri, 05 Feb 2010 10:02:55 +030010 2010, 10:02:55

8 ответов


0

Это можно смоделировать как проблему с графиком. Вы можете думать о словах как о узлах графа, и два узла связаны тогда и только тогда, когда они имеют одинаковую длину и отличаются на один символ.

Вы можете предварительно обработать словарь и создать этот график, который должен выглядеть следующим образом:

   stack  jack
    |      |
    |      |
   smack  back -- pack -- pick

Затем вы можете сопоставить слово со узлом, представляющим слово, для этого вы можете использовать хеш-таблицу с балансировкой высоты BST ...

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

Таким образом, вы можете обобщить алгоритм следующим образом:

preprocess the dictionary and create the graph.
Given the two inputs words w1 and w2
if length(w1) != length(w2)
 Not possible to convert
else
 n1 = get_node(w1)
 n2 = get_node(w2)

 if(path_exists(n1,n2))
   Possible and nodes in the path represent intermediary words
 else
   Not possible
ответил codaddict 5 FebruaryEurope/MoscowbFri, 05 Feb 2010 10:05:30 +0300000000amFri, 05 Feb 2010 10:05:30 +030010 2010, 10:05:30
0

подход графа codaddict действителен, хотя для построения каждого графа требуется O (n ^ 2) времени, где n - количество слов заданной длины. Если это проблема, вы можете создать bk- дерево гораздо эффективнее, что позволяет находить все слова с заданным расстоянием редактирования (в данном случае 1) целевого слова.

ответил Nick Johnson 8 FebruaryEurope/MoscowbMon, 08 Feb 2010 13:38:38 +0300000000pmMon, 08 Feb 2010 13:38:38 +030010 2010, 13:38:38
0

Создайте граф с каждым узлом, представляющим слово в словаре. Добавьте ребро между двумя узлами слова, если их соответствующие слова находятся на расстоянии редактирования 1. Тогда минимальное количество необходимых преобразований будет равно длине кратчайшего пути между узлом источника и узлом назначения.

ответил prasadvk 16 AMpTue, 16 Apr 2013 04:30:34 +040030Tuesday 2013, 04:30:34
0

Я не думаю, что это расстояние редактирования.

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

ответил Yuliy 5 FebruaryEurope/MoscowbFri, 05 Feb 2010 10:05:30 +0300000000amFri, 05 Feb 2010 10:05:30 +030010 2010, 10:05:30
0

Вы можете просто использовать рекурсивное обратное отслеживание, но это далеко не самое оптимальное решение.

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only
# one letter at a time.  The new word you get in each step must be in the
# dictionary.

# def transform(english_words, start, end):

# transform(english_words, 'damp', 'like')
# ['damp', 'lamp', 'limp', 'lime', 'like']
# ['damp', 'camp', 'came', 'lame', 'lime', 'like']


def is_diff_one(str1, str2):
    if len(str1) != len(str2):
        return False

    count = 0
    for i in range(0, len(str1)):
        if str1[i] != str2[i]:
            count = count + 1

    if count == 1:
        return True

    return False


potential_ans = []


def transform(english_words, start, end, count):
    global potential_ans
    if count == 0:
        count = count + 1
        potential_ans = [start]

    if start == end:
        print potential_ans
        return potential_ans

    for w in english_words:
        if is_diff_one(w, start) and w not in potential_ans:
            potential_ans.append(w)
            transform(english_words, w, end, count)
            potential_ans[:-1]

    return None


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like'])
transform(english_words, 'damp', 'lame', 0)
ответил Pradeep Vairamani 17 +03002015-10-17T00:12:21+03:00312015bEurope/MoscowSat, 17 Oct 2015 00:12:21 +0300 2015, 00:12:21
0

Это код C # для решения проблемы с использованием BFS:

//use a hash set for a fast check if a word is already in the dictionary
    static HashSet<string> Dictionary = new HashSet<string>();
    //dictionary used to find the parent in every node in the graph and to avoid traversing an already traversed node
    static Dictionary<string, string> parents = new Dictionary<string, string>();

    public static List<string> FindPath(List<string> input, string start, string end)
    {
        char[] allcharacters = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

        foreach (string s in input)
            Dictionary.Add(s);
        List<string> currentFrontier = new List<string>();
        List<string> nextFrontier = new List<string>();
        currentFrontier.Add(start);
        while (currentFrontier.Count > 0)
        {
            foreach (string s in currentFrontier)
            {
                for (int i = 0; i < s.Length; i++)
                {
                    foreach (char c in allcharacters)
                    {
                        StringBuilder newWordBuilder = new StringBuilder(s);
                        newWordBuilder[i] = c;
                        string newWord = newWordBuilder.ToString();
                        if (Dictionary.Contains(newWord))
                        {
                            //avoid traversing a previously traversed node
                            if (!parents.Keys.Contains(newWord))
                            {
                                parents.Add(newWord.ToString(), s);
                                nextFrontier.Add(newWord);
                            }

                        }
                        if (newWord.ToString() == end)
                        {
                            return ExtractPath(start, end);

                        }
                    }
                }
            }
            currentFrontier.Clear();
            currentFrontier.Concat(nextFrontier);
            nextFrontier.Clear();
        }
        throw new ArgumentException("The given dictionary cannot be used to get a path from start to end");
    }

    private static List<string> ExtractPath(string start,string end)
    {
        List<string> path = new List<string>();
        string current = end;
        path.Add(end);
        while (current != start)
        {
            current = parents[current];
            path.Add(current);
        }
         path.Reverse();
         return path;
    }
ответил Muhammad Adel 11 AMpFri, 11 Apr 2014 00:18:09 +040018Friday 2014, 00:18:09
0

Я не думаю, что нам нужен график или какая-то другая сложная структура данных. Моя идея - загрузить словарь как HashSet и использовать contains() метод, чтобы узнать, существует ли слово в словаре или нет.

Пожалуйста, проверьте этот псевдокод , чтобы увидеть мою идею:

Two words are given: START and STOP. 
//List is our "way" from words START to STOP, so, we add the original word to it first.
    list.add(START);
//Finish to change the word when START equals STOP.
    while(!START.equals(STOP))
//Change each letter at START to the letter to STOP one by one and check if such word exists.
    for (int i = 0, i<STOP.length, i++){
        char temp = START[i];
        START[i] = STOP[i];
//If the word exists add a new word to the list of results. 
//And change another letter in the new word with the next pass of the loop.
        if dictionary.contains(START)
           list.add(START)
//If the word doesn't exist, leave it like it was and try to change another letter with the next pass of the loop.
        else START[i] = temp;}
    return list;

Как я понимаю, мой код должен работать так:

Вход : DAMP, LIKE

Выход : DAMP, LAMP, LIMP, LIME, LIKE

Ввод : НАЗАД, ВЫБОР

Вывод : НАЗАД, УПАКОВКА, ВЫБОР

ответил Boris 5 TueEurope/Moscow2017-12-05T10:38:42+03:00Europe/Moscow12bEurope/MoscowTue, 05 Dec 2017 10:38:42 +0300 2017, 10:38:42
0

Это явно проблема перестановки. Использование графа является излишним. В постановке задачи отсутствует одно важное ограничение; что вы можете изменить каждую позицию только один раз . Это тогда делает неявным, что решение находится в пределах 4 шагов. Теперь все, что нужно решить, это последовательность операций замены:

Operation1 = изменить "H" на "T"
Operation2 = изменить «E» на «A»
Operation3 = изменить «A» на «I»
Operation4 = изменить "D" на "L"

Решение, последовательность операций, представляет собой некоторую перестановку строки «1234», где каждая цифра представляет позицию заменяемого символа. например «3124» указывает, что сначала мы применяем операцию 3, затем операцию 1, затем операцию 2, а затем операцию 4. На каждом шаге, если результирующего слова нет в словаре, переходите к следующей перестановке. Разумно тривиально. Кто-нибудь код?

ответил ChampCoda 14 FebruaryEurope/MoscowbTue, 14 Feb 2012 23:52:49 +0400000000pmTue, 14 Feb 2012 23:52:49 +040012 2012, 23:52:49

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132