leetcode127. Word Ladder

Galence 发布于2019-08-15 11:11 / 1852人阅读

摘要：但是这种要遍历所有的情况，哪怕是已经超过最小操作次数的情况，导致代码超时。其实从另一个角度来说，这道题可以看做是广度优先算法的一个展示。按上文中的题目为例，可以将广度优先算法写成以下形式。

题目要求

Given two words (beginWord and endWord), and a dictionary"s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

假设输入两个单词beginWord，endWord以及一个字典。每一次操作只能对当前单词修改一个字符成为字典中的一个单词。问至少需要多少次操作可以将beginWord转化为endWord。如果不可转换则返回0。

思路与代码

其实如果从递归的角度来看，并非不可以实现。每一种普遍情况也就是将当前单词修改一个字符成为当前字典中的一个单词。但是这种要遍历所有的情况，哪怕是已经超过最小操作次数的情况，导致代码超时。其实从另一个角度来说，这道题可以看做是广度优先算法的一个展示。

按上文中的题目为例，可以将广度优先算法写成以下形式。

    hit
    /
  hot
  / 
dot  lot
/    / 
dog  log
/     /
cog  cog

也就是说，将每一层上可以生成的单词全部列出来，然后再逐层遍历，一旦出现一个单词等于endWord，那么遍历终止，将当前遍历的次数返回。这里要注意的是，需要将已经遍历的单词记录下来，从而不会发生重复的情况。

代码

    //和字典中单词比较是否可以转换
    public boolean canTransform(String word1, String word2){
         for(int i = 0, count=0 ; i1) return false;
         }
         return true;
     }
     
     public int ladderLength(String beginWord, String endWord, List wordList){
         Queue q = new LinkedList();
         q.add(beginWord);
         int steps = 0;
         while(!q.isEmpty()){
             int size = q.size();
             for(int i = 0 ;i iterator = wordList.iterator() ; iterator.hasNext();){
                     String current = iterator.next();
                     if(canTransform(current, temp)){
                         iterator.remove();
                         q.offer(current);
                     }
                 }
             }
            steps++;

         }
         return 0;
     }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

服务器托管私有云 Ladder cdn服务器ip127 Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67597.html

leetcode126. Word Ladder II

摘要：题目要求相比于，要求返回所有的最短路径。至于如何生成该有向图，则需要通过广度优先算法，利用队列来实现。将每一层的分别入栈。如果遇到则至该层结尾广度优先算法结束。通过这种方式来防止形成圈。题目要求 Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transfo...

cooxer 2019-08-15 11:13 评论0 收藏0
[Leetcode] Word Ladder 单词爬梯

摘要：另外，为了避免产生环路和重复计算，我们找到一个存在于字典的新的词时，就要把它从字典中移去。代码用来记录跳数控制来确保一次循环只计算同一层的节点，有点像二叉树遍历循环这个词从第一位字母到最后一位字母循环这一位被替换成个其他字母的情况 Word Ladder Given two words (beginWord and endWord), and a dictionary, find t...

pinecone 2019-08-14 12:24 评论0 收藏0
[LeetCode/LintCode] Word Ladder

摘要：使用，利用其按层次操作的性质，可以得到最优解。这样可以保证这一层被完全遍历。每次循环取出的元素存为新的字符串。一旦找到和相同的字符串，就返回转换序列长度操作层数，即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...

张金宝 2019-08-14 15:27 评论0 收藏0
[LeetCode] 126. Word Ladder II

摘要：存放过程中的所有集合为所有的结尾，则顺序存放这个结尾对应的中的所有存放同一个循环的新加入的，在下一个循环再依次对其中元素进行进一步的把首个字符串放入新，再将放入，并将键值对放入，进行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

wayneli 2019-08-14 14:27 评论0 收藏0
127. Word Ladder

摘要：题目解答主要解题思路的，把每一种可能的都放进去试，看能不能有一条线边到代码当然，这样的时间还不是最优化的，如果我们从两头扫，扫到中间任何一个能够串联起来都可以，如果没有找到可以串联的那么返回。题目：Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...

forsigner 2019-08-14 14:25 评论0 收藏0