`

LeetCode 127 - Word Ladder

 
阅读更多

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

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.

Solution:

Breadth First Search.

起个好的变量名多么的重要啊。我看到网上写的好多代码,那变量名起的太有混淆的反作用了。

 

  • 和当前单词相邻的单词是:对当前单词改变一个字母且在字典中存在的单词
  • 找到一个单词的相邻单词,加入bfs队列后,要从字典中删除,因为不删除的话会造成类似于hog->hot->hog的死循环。而删除对求最短路径没有影响,因为我们第一次找到该单词肯定是最短路径,即使后面其他单词也可能转化得到它,路径肯定不会比当前的路径短(如果要输出所有最短路径,则不能立即从字典中删除)
  • bfs队列中用width==0来标识层与层的间隔,每次碰到width==0,遍历深度+1

这个算法中最坏情况是把所有长度为L的字符串都看一下,或者把字典中的字符串都看一下,而长度为L的字符串总共有26^L,所以时间复杂度是O(min(26^L, size(dict)),空间上需要存储访问情况,也是O(min(26^L, size(dict))。

public int ladderLength(String start, String end, HashSet<String> dict) {
    if (dict == null || dict.size() == 0) return 0;
    Queue<String> queue = new LinkedList<String>();
    queue.offer(start);
    dict.remove(start);
    int depth = 1; // ladder的深度
    int width = 1; // 层的宽度,即每一层变换的单词的总数量

    while(!queue.isEmpty()) {
        char[] str = queue.poll().toCharArray();
        for (int i=0; i < str.length; i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if(str[i] == c) continue;
                char tmp = str[i];
                str[i] = c;
                String word = new String(str);
                if (word.equals(end)) return depth + 1;
                if (dict.remove(word)){ //当该单词在词典中,删除并返回true;若不存在该单词则返回false
                    queue.offer(word);
                }
                str[i] = tmp;
            }
        }
        if(--width == 0) {
            width = queue.size(); //更新为下一层变换的单词的数量
            depth++;
        }
    }
    return 0;
}

 

C++的代码:

int ladderLength(string start, string end, unordered_set<string> &dict) {
    queue<string> q;
    q.push(start);
    dict.erase(start);
    int len = 1;
    while(!q.empty()) {
        int size = q.size();
        for(int i=0; i<size; i++) {
            string s = q.front();
            q.pop();
            for(int j=0; j<s.size(); j++) {
                char ch = s[j];
                for(char c='a'; c<='z'; c++) {
                    if(c == ch) continue;
                    s[j] = c;
                    if(s == end) return len+1;
                    if(dict.count(s)) {
                        q.push(s);
                        dict.erase(s);
                    }
                }
                s[j] = ch;
            }
        }
        len++;
    }
    return 0;
}

 

分享到:
评论

相关推荐

    python-leetcode题解之127-Word-Ladder

    python python_leetcode题解之127_Word_Ladder

    leetcode1-240题中文题解,md格式,java

    1. leetCode-126-Word-LadderII.md:这涉及到第126题,词梯问题,通常是一个字符串转换问题,目标是找到两个单词之间的最短转换序列,每次只改变一个字母。 2. leetcode-224-Basic-Calculator.md:这是第224题,基础...

    python-leetcode题解之126-Word-Ladder-II

    python python_leetcode题解之126_Word_Ladder_II

    LeetCode题解 - Java语言实现-181页.pdf

    6. Word Ladder 单词梯是一个字符串问题,要求将一个单词转换为另一个单词,并且每次转换只能改变一个字符。可以使用广度优先搜索或深度优先搜索来解决该问题。 7. Median of Two Sorted Arrays in Java 两个排序...

    leetcode多少题-word_ladder:字梯

    leetcode 多少题带有堆栈和队列的字梯 您将针对 Lewis Carroll ...在本作业中,您将实现一个函数word_ladder来生成这些字梯。 有许多可能的算法来生成字梯,但一个简单的算法使用堆栈和队列的组合,如

    leetcode316-LeetCode:leetcode的解决方案

    leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...

    126.Word Ladder II 词语阶梯二【LeetCode单题讲解系列】

    126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】

    word ladder

    经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目

    java-leetcode-solutions:一些LeetCode问题的解决方案

    例如,`WordLadder.java`可能涉及到词链问题,需要理解图的邻接矩阵或邻接表表示。 6. **字符串处理**:如模式匹配、字符串反转、最长公共前缀等。`ValidPalindrome.java`可能涉及字符串的比较和操作。 7. **位...

    leetcode-python:python中的leetcode

    力扣 Python 解决方案Leetcode 是准备技术编码面试的...特别案例: Word Ladder II,我的 AC 代码比这个 repo 中的代码慢得多。 但是这个 repo 中的一个得到了 TLE,不知道为什么。 任何想法都将受到高度赞赏。 谢谢!

    LeetCode题解(java语言实现).pdf

    * Word Ladder:该题目要求将一个单词转换成另一个单词,实现方法使用了广度优先搜索算法。 二、树和图 * Median of Two Sorted Arrays Java:该题目要求找到两个排序数组的中位数,实现方法使用了二分查找算法。 ...

    leetcode刷题LeetCode1500道单词接龙Python3

    在LeetCode上,单词接龙类问题可能表现为“Anagrams”(同字母异序词)或者“Word Ladder”(单词阶梯),这些题目要求高效地搜索满足条件的单词序列。 【压缩包子文件的文件名称列表】"LeetCode-main"可能包含了一...

    Amazon亚麻 最新leetcode tag题

    5. **搜索和回溯**:对于“NumberofIslands”、“WordLadder”等题目,应聘者必须运用搜索算法,如广度优先搜索(BFS)、深度优先搜索(DFS)以及回溯算法来寻找解决方案。 6. **动态规划和贪心算法**:...

    Leetcode代码以及解答(2)

    Word Ladder **知识点:** - **问题描述:** - 找到由开始到结尾的字符串的转换字符串集合,中间的转换字符串都要在给定的列表中,并且每一步只能改变一个字符。 - **解决方案分析:** - **原始方法:** - ...

    leetcode代码200题c++

    8. **Word Ladder II**:这是一个词链问题,涉及到广度优先搜索和回溯法,寻找从一个单词转换到另一个单词的最短路径。 9. **Regular Expression Matching**:这个涉及到字符串匹配和动态规划。实现一个函数来判断...

    LeetCode解题总结

    9.1 单词变换路径(Word Ladder) 9.1.1 是否存在变换路径 9.1.2 所有最短变换路径9.2 包围区域 10. 深度优先搜索 10.1 N皇后问题 10.2 恢复IP地址 10.3 集合元素之和 10.3.1 元素可以重复 10.3.2 元素不可重复 ...

    Coding Interview In Java

    leetcode Java 246 題目及解答 (英文) Contents 1 Rotate Array in Java 15 2 Reverse Words in a String II 19 3 Evaluate Reverse Polish Notation 21 4 Isomorphic Strings 25 5 Word Ladder 27 6 Word Ladder ...

    javalruleetcode-leetcode:更多信息请访问Gitbook:https://wentao-shao.gitbook.io/

    java lru leetcode ...Ladder Add Two Numbers Matrix Spiral Matrix Mergesort [Algorithm Swap](Mergesort/Algorithm swap.md) Numbers Queue Stack Toposort Trie Tree Two Pointers Union Find

    LeetCodeSolutions

    6. **图论**:深度优先搜索(DFS)和广度优先搜索(BFS)在解决图问题如"Word Ladder"时必不可少。 7. **位运算**:在某些问题中,如"Number of 1 Bits",位运算可以提供高效的解决方案。 8. **设计模式**:工厂...

Global site tag (gtag.js) - Google Analytics