字符串-通过有效单词将一个单词转换为另一个单词的算法

我遇到了这种编辑距离问题的变体:

设计一种将源词转换为目标词的算法。 例如:从头到尾,在每个步骤中,您只能替换一个字符,并且该单词必须有效。 您将得到一本字典。

显然这是编辑距离问题的一种变体,但是在编辑距离中,我并不关心单词是否有效。 因此,如何添加此要求以编辑距离。

gameover asked 2020-07-30T03:59:55Z
9个解决方案
45 votes

可以将其建模为图问题。 您可以将单词视为图的节点,并且当且仅当它们的长度相同且相差一个字符时,才将两个节点连接起来。

您可以预处理字典并创建此图,应如下所示:

   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 answered 2020-07-30T04:00:22Z
12 votes

codaddict的图方法是有效的,尽管构建每个图需要O(n ^ 2)时间,其中n是给定长度的单词数。 如果存在问题,则可以更有效地构建bk树,从而可以找到目标词具有给定编辑距离(在本例中为1)的所有词。

Nick Johnson answered 2020-07-30T04:00:42Z
4 votes

创建一个图,每个节点代表字典中的单词。 如果两个单词节点之间的对应单词的编辑距离为1,则在它们之间添加边。然后,所需的最少转换次数将是源节点和目标节点之间的最短路径的长度。

prasadvk answered 2020-07-30T04:01:02Z
2 votes

我不认为这是编辑距离。

我认为可以使用图表来完成。 只需从字典中构造一个图形,然后尝试使用您喜欢的图形遍历算法导航到目标即可。

Yuliy answered 2020-07-30T04:01:27Z
1 votes

您可以简单地使用递归回溯,但这远非最佳解决方案。

# 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 answered 2020-07-30T04:01:47Z
0 votes

这是使用BFS解决问题的C#代码:

//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 Soliman answered 2020-07-30T04:02:07Z
0 votes

我认为我们不需要图或其他复杂的数据结构。 我的想法是将字典加载为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

Boris answered 2020-07-30T04:02:53Z
-1 votes

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;    
    }
}
Piyush Datani answered 2020-07-30T04:03:09Z
-2 votes

这显然是一个排列问题。 使用图形是过大的。 问题陈述缺少一项重要约束; 每个位置只能更改一次。 这样就隐含了解决方案在4个步骤之内。 现在只需确定替换操作的顺序即可:

操作1 =将“ H”更改为“ T”
Operation2 =将“ E”更改为“ A”
Operation3 =将“ A”更改为“ I”
Operation4 =将“ D”更改为“ L”

解决方案(操作顺序)是字符串“ 1234”的某种排列,其中每个数字代表要替换的字符的位置。 例如 “ 3124”表示首先应用操作3,然后应用操作1,然后应用操作2,然后应用操作4。在每个步骤中,如果结果单词不在字典中,请跳至下一个排列。 合理的琐碎。 编码任何人?

ChampCoda answered 2020-07-30T04:03:51Z
translate from https://stackoverflow.com:/questions/2205540/algorithm-to-transform-one-word-to-another-through-valid-words