【华为OD机试】真题E卷-单词接龙（Java）

在这篇文章中，我们将讨论一个经典的编程题目——单词接龙。单词接龙是一种游戏，其中每个参与者需要接上一个单词的最后一个字母来形成一个新的单词。为了实现这一功能，我们将使用Java语言来编写程序。

问题描述

假设我们有一个单词列表，参与者需要从这个列表中选择单词，并且每个单词必须以之前所用单词的最后一个字母开头。例如，若前一个单词为“apple”，那么下一个单词必须以“e”开头，如“elephant”。我们需要实现一个方法来检查这些单词是否可以组成合法的接龙序列。

代码示例

以下是实现单词接龙的基本思路和代码：

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordChain {

    // 方法检查单词接龙是否合法
    public boolean isValidWordChain(List<String> words) {
        // 检查输入是否为空
        if (words == null || words.size() == 0) {
            return false;
        }

        // 使用HashSet存储已使用的单词
        Set<String> usedWords = new HashSet<>();
        usedWords.add(words.get(0));  // 首个单词标记为已使用

        for (int i = 1; i < words.size(); i++) {
            String currentWord = words.get(i);
            String lastWord = words.get(i - 1);

            // 检查当前单词是否已被使用
            if (usedWords.contains(currentWord)) {
                return false; // 单词重复
            }

            // 检查当前单词的起始字母和上一个单词的最后一个字母是否匹配
            if (currentWord.charAt(0) != lastWord.charAt(lastWord.length() - 1)) {
                return false; // 单词不匹配
            }

            usedWords.add(currentWord); // 标记当前单词为已使用
        }

        return true; // 若所有条件都满足，返回true
    }

    public static void main(String[] args) {
        WordChain wordChain = new WordChain();

        List<String> words = List.of("apple", "elephant", "tiger", "rabbit", "taco");

        // 检查单词接龙是否合法
        boolean result = wordChain.isValidWordChain(words);
        if (result) {
            System.out.println("这些单词可以组成合法的接龙。");
        } else {
            System.out.println("这些单词不能组成合法的接龙。");
        }
    }
}

代码分析

1. 方法 isValidWordChain:
2. 接收一个单词列表作为参数。
3. 使用 HashSet 来跟踪已使用的单词，确保每个单词只能使用一次。
4. 循环遍历单词列表，从第二个单词开始，检查每个单词是否符合接龙的规则。

5. 对于每一个单词，首先检查它是否已经在 usedWords 中，然后检查它的首字母是否与前一个单词的尾字母相同。

6. 主方法:

7. 创建 WordChain 的实例，定义一个单词列表，并调用 isValidWordChain 方法进行验证。
8. 根据结果输出是否合法的信息。

总结

上述代码实现了一个简单的单词接龙的功能。通过使用 HashSet 来管理已使用的单词，可以有效地防止单词的重复使用，同时确保规则的完整性。在实际应用中，可以根据需求进一步扩展功能，比如读取用户输入的单词列表、增加单词字典进行有效性检查等。这种简单的游戏逻辑不仅可以帮助我们巩固字符串操作的基础知识，同时也为我们提供了思考数据结构如何运用到实际问题中的机会。