如何用Java高效判断一个单词是否为NICE单词？

兄弟，我太懂你这种“逻辑全对但一跑长单词用例就超时”的憋屈了！咱们直接用KMP算法里的核心思想——**部分匹配表（Next数组）**来解决，把时间复杂度从暴力的O(n²)直接降到线性的O(n)，长单词也能秒出结果。

NICE单词定义 #

若一个单词拥有相同的真前缀（proper prefix）和真后缀（proper suffix），则该单词为NICE单词。真前缀或真后缀的长度不得与单词本身长度相同。

示例 #

• manama是NICE单词，因其真前缀和真后缀均为“ma”，输出“NICE”
• panama不是NICE单词，输出“NOT”

性能优化方案 #

问题根源 #

之前的暴力解法应该是枚举所有可能的前后缀长度（从1到单词长度-1），逐个比较前缀和后缀是否相等。这种方法在单词很长时，每次比较都要扫一遍子串，时间开销直接爆炸。

核心思路 #

KMP算法的Next数组专门用来记录每个位置前的子串的最长相等真前缀后缀长度。对于整个单词来说，next[单词长度-1]（数组从0开始）就是我们要找的最长匹配长度——只要这个长度大于0，就说明存在符合要求的真前缀后缀，单词就是NICE的；反之则不是。

Java代码实现 #

public static String checkNiceWord(String word) {
    int wordLen = word.length();
    // 长度<=1的单词没有真前缀/后缀，直接返回NOT
    if (wordLen <= 1) {
        return "NOT";
    }
    
    int[] next = new int[wordLen];
    int prefixLen = 0; // 当前匹配的前缀长度
    
    // 构建Next数组
    for (int i = 1; i < wordLen; i++) {
        // 不匹配时，回退到上一个匹配的前缀位置
        while (prefixLen > 0 && word.charAt(i) != word.charAt(prefixLen)) {
            prefixLen = next[prefixLen - 1];
        }
        // 匹配成功，前缀长度+1
        if (word.charAt(i) == word.charAt(prefixLen)) {
            prefixLen++;
            next[i] = prefixLen;
        }
    }
    
    // 判断最长相等真前后缀长度是否大于0
    return next[wordLen - 1] > 0 ? "NICE" : "NOT";
}

为什么这能提速？ #

构建Next数组的过程只需要遍历单词一次，是线性时间复杂度O(n)。相比暴力法每次比较都要重复扫描子串，这个方法不管单词多长，都能高效完成检测——哪怕是几万字符的长单词，也能瞬间给出结果。

拿示例来说：

• manama的Next数组最后一位是2（对应长度为2的"ma"），所以返回"NICE"
• panama的Next数组最后一位是0，所以返回"NOT"

内容的提问来源于stack exchange，提问作者user9291964