Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

Force buckle 127 words solitaire as follows:

BeginWord -> s1 -> s2 ->… – > sk:

  • Each pair of adjacent words is separated by only one letter.
  • for1 <= i <= k, eachsiAll inwordListIn the. Pay attention to,beginWordDon’t need towordListIn the.
  • sk == endWord

You are given two words beginWord and endWord and a dictionary wordList that returns the number of words in the shortest conversion sequence from beginWord to endWord *. If no such conversion sequence exists, return 0.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] A minimum conversion sequence is "hit" - > "hot" - > "dot" - > "dog" - > "cog", return it the length of 5.Copy the code

A, thinking

This question is very similar to the previous question likou 126 – Word Solitarong II, which is to replace the characters in beginWord one by one to ensure that the replaced characters in the wordList, the final new character beginWord’ is equal to endWord, to find the shortest transformation path node number

Since we only need to know the number of nodes in the shortest path, we don’t need to spend time storing specific nodes.

Of course, the key idea of this problem is still to build a directed graph and find the number of shortest paths from the starting point to the key point. Here, example 1 is used as an example. Since only one character can be replaced at a time, we can easily build the following digraph 👇

Using breadth traversal we can generate the graph above, but we need to think about a question: how do we make sure we get the shortest path?

In fact, to solve this problem is very simple, we only need to ensure the following two things

  1. When the next character after the replacement is determined, the current character is removed from the path to prevent backtracking
  2. The shortest path is the one who meets the end first. That is, just show upendWordImmediately return. (Because the long path must reach its destination later.)

Second, the implementation

The implementation code

Diff () : a custom function to compare the number of different characters in two strings

Note that the next node can be fetched from the result set wordList (as long as it differs by one character from the current one)

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // Create a dictionary
        Set<String> dict = new HashSet<>(wordList);
        if(! dict.contains(endWord))return 0;
        Queue<String> path = new LinkedList<>();
        int level = 1;
        path.add(beginWord);

        while(! path.isEmpty()) {int size = path.size();
            for (int i = 0; i < size; i++) {
                // The current string replaces a string
                String currWord = path.remove();
                if (currWord.equals(endWord)) {
                    return level;
                }
                // walk through the dictionary
                Iterator<String> iterator = dict.iterator();
                while (iterator.hasNext()){
                    String nextWord = iterator.next();
                    if (diff(currWord, nextWord)) {
                        path.add(nextWord);
                        iterator.remove();
                    }
                }
            }
            level++;
        }
        return 0;
    }

    // Returns a different number of characters
    public boolean diff(String a, String b){
        int count = 0;
        char[] arr1 = a.toCharArray();
        char[] arr2 = b.toCharArray();
        for (int i=0; i<arr1.length; i++)
            if(arr1[i] ! = arr2[i]) count++;return count == 1;
    }
Copy the code

The test code

public static void main(String[] args) {
    String being = "hit";
    String end = "cog";
    List<String> list = Arrays.asList("hot"."dot"."dog"."lot"."log"."cog");
    int ret = new Number127().ladderLength(being, end, list);
    System.out.println(ret);
}
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section