LeetCode 127. Word Ladder

Problem:

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

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

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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:

Today I knew that building an adjacency map is a stupid, stupid solution when you have way more elements than path.

public class Solution {
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        wordList.add(endWord);
        Queue<String> current = new LinkedList<String>();
        int step = 1;
        current.offer(beginWord);
        while (!current.isEmpty()) {
            int size = current.size();
            while (size > 0) {
                String word = current.poll();
                if (word.equals(endWord))
                    return step;
                for (int i = 0; i < word.length(); i++) {
                    char[] arr = word.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c;
                        String check = new String(arr);
                        if (!check.equals(word) && wordList.contains(check)) {
                            current.offer(check);
                            wordList.remove(check);
                        }
                    }
                }
                size--;
            }
            step++;
        }
        return 0;
    }
}

7 thoughts on “LeetCode 127. Word Ladder”

  1. 加強優化面部輪廓,可被身體完全吸引,能自然地修飾面部輪廓 功效可長達24個月以上 JUVEDERM的特點: 效果立即可見 非永久性 非手術性 安全有效 效果自然 JUVEDERM獲歐盟(CE)及美國及藥物管理局(FDA)認證 首先及唯一獲得FDA認證在首次療程後能維持長達一年2-4功效 新世代專員Hylacross科技為產品帶來獨特的物理特質,包括凝聚力、支撐力及柔順度 8點提升 這是一套由全球著名醫學美容醫生Dr. Maurício de Maio,以JUVÉDERM®系列透明質酸產品為基礎而研發的面部優化療程,藉著簡單程序便達致面部優化效果,不需進行手術,減低風險。 此療程會根據病人的個別情況,重點針對面部8個最常因流失膠原蛋白及彈性纖維而凹陷的位置,再依據特定的順序,從顴骨至下巴位置配合JUVÉDERM®系列的透明質酸產品進行療程,從而改善這些位置的豐盈度及滑溜度,全面性優化面部輪廓。

  2. 有關雙眼皮手術、割雙眼皮、上眼皮手術、雙眼皮成形術、縫雙眼皮、訂書針雙眼皮等一些詳細敘述或似是而非或有爭議的事項。

Leave a Reply

Your email address will not be published. Required fields are marked *