题解 | #牛群最短移动序列#

牛群最短移动序列

https://www.nowcoder.com/practice/6473462e05ac4665baec04caf628abdd

一、知识点:

BFS、队列、HashSet

二、文字分析:

使用了一个队列来进行广度优先搜索。首先,将起始词加入队列,然后开始循环遍历队列。每次从队列中取出一个词,将其进行变换,产生所有可能的下一步词,并将这些下一步词加入队列。如果某个下一步词与目标词完全相同,表示找到了最短移动序列,返回当前级别+1。如果队列为空仍然没有找到目标词,说明无法转换到最终目标,返回0。

三、编程语言:

java

四、正确代码:

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param beginWord string字符串
     * @param endWord string字符串
     * @param wordList string字符串一维数组
     * @return int整型
     */
    public int ladderLength(String beginWord, String endWord, String[] wordList) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(wordList));
        if (!wordSet.contains(endWord)) {
            return 0; // 结束词不在字典中,无法转换
        }
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        
        int level = 0; // 转换序列的级别
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                
                char[] arr = word.toCharArray();
                
                for (int j = 0; j < arr.length; j++) {
                    char originalChar = arr[j];
                    
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        if (ch == originalChar) {
                            continue;
                        }
                        
                        arr[j] = ch;
                        
                        String newWord = new String(arr);
                        
                        if (newWord.equals(endWord)) {
                            return level + 1; // 找到最终目标,返回级别+1
                        }
                        
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord); // 确保不会重复访问已经入队列的单词
                        }
                    }
                    
                    arr[j] = originalChar; // 恢复原始字符
                }
            }
        }
        
        return 0; // 无法转换到最终目标
    }
}

全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务