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

Ответ 1

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

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

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

Затем вы можете сопоставить слово со словом node, представляющим слово, для этого вы можете использовать хеш-таблицу, сбалансированную по высоте 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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 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)

Ответ 6

Это код С# для решения проблемы с использованием 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;
    }

Ответ 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, PICK

Выход: BACK, PACK, PICK

Ответ 8

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;    
    }
}

Ответ 9

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

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

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