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

Question

Я сталкивался с этой проблемой edit-distance problem:

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

Ясно, что это вариация проблемы расстояние редактирования , но при расстоянии редактирования мне все равно, является ли слово правильным или нет. Так как мне добавить это требование для редактирования расстояния.

Answer 1

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

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

   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

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

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

# 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)

Answer 6

class Solution {
    //static int ans=Integer.MAX_VALUE;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashMap<String,Integer> h=new HashMap<String,Integer>();
        HashMap<String,Integer> h1=new HashMap<String,Integer>();
        for(int i=0;i<wordList.size();i++)
        {
            h1.put(wordList.get(i),1);
        }
        int count=0;
        Queue<String> q=new LinkedList<String>();
        q.add(beginWord);
        q.add("-1");
        h.put(beginWord,1);
        int ans=ladderLengthUtil(beginWord,endWord,wordList,h,count,q,h1);
        return ans;
    }
    public int ladderLengthUtil(String beginWord, String endWord, List<String> wordList,HashMap<String,Integer> h,int count,Queue<String> q,HashMap<String,Integer> h1)
    {  
        int ans=1;
        while(!q.isEmpty()) 
        {
            String s=q.peek();
            q.poll();
            if(s.equals(endWord))
            {
                return ans;   
            }
            else if(s.equals("-1"))
            {
                if(q.isEmpty())
                {                    
                    break;
                }
                ans++;                
                q.add("-1");
            }
            else
            {
                for(int i=0;i<s.length();i++)
                {
                        for(int j=0;j<26;j++)
                        {
                            char a=(char)('a'+j);
                            String s1=s.substring(0,i)+a+s.substring(i+1);
                            //System.out.println("s1 is "+s1);
                            if(h1.containsKey(s1)&&!h.containsKey(s1))
                            {
                                h.put(s1,1);
                                q.add(s1);
                            }
                        }
                }
            }
        }
        return 0;    
    }
}

Answer 7

Я не думаю, что нам нужен график или какая-то другая сложная структура данных. Моя идея состоит в том, чтобы загрузить словарь как 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

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

Выход : BACK, PACK, PICK

Answer 8

Это код 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;
    }

Answer 9

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

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

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