leetcode
leetcode 451 ~ 500
单词缩写

单词缩写

难度:

标签:

题目描述

代码结果

运行时间: 60 ms, 内存: 20.2 MB


/*
 * 题目思路:
 * 1. 使用Java Stream对数组进行遍历。
 * 2. 对于每个单词,使用map函数进行缩写处理。
 * 3. 最终使用forEach输出每个缩写后的单词。
 */
 
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
 
public class WordAbbreviationStream {
    public static String abbreviateWord(String word) {
        if (word.length() <= 2) {
            return word; // 如果单词长度小于等于2,则直接返回原单词
        }
        int length = word.length() - 2; // 中间部分的长度
        return word.charAt(0) + String.valueOf(length) + word.charAt(word.length() - 1);
    }
 
    public static void main(String[] args) {
        List<String> words = Arrays.asList("international", "local", "a", "ab");
        words.stream()
             .map(WordAbbreviationStream::abbreviateWord)
             .forEach(System.out::println);
    }
}
 

解释

方法:

此题解的核心思路是缩写给定列表中的单词。如果单词长度小于4,不进行缩写。对于其他单词,从最短可能的缩写开始尝试,直到找到一个不与其他单词的缩写冲突的缩写。此过程使用两个主要数据结构:'cache'用来存储每个缩写对应的单词(如果存在冲突,则设置为空字符串),'ret'用来存储每个单词对应的最终缩写结果。函数 'ga' 用于生成一个单词的缩写,'add' 函数尝试为一个单词找到一个合适的缩写并处理冲突。最后,根据输入单词的顺序返回缩写结果。

时间复杂度:

O(n * k^2) 其中 n 是单词数量,k 是单词的平均长度

空间复杂度:

O(n * k) 其中 n 是单词数量,k 是单词的平均长度

代码细节讲解

🦆
在函数`ga`中,`np`参数的作用是什么,以及如何决定其值?
`np`参数在函数`ga`中代表单词的前缀长度,这意味着在生成缩写时会保留单词的前`np`个字符。通过改变`np`的值,可以生成不同长度的缩写。这个值通常从1开始增加,尝试生成尽可能短的有效缩写,直到找到一个不与任何其他单词的缩写冲突的缩写为止。
🦆
如何确保缩写`a`在`cache`中的管理不会导致错误覆盖或丢失原有数据?
为了防止错误覆盖或丢失数据,当缩写`a`已存在于`cache`中并且与另一个单词冲突时,原始代码不会简单地覆盖缩写。相反,如果`cache[a]`已经有值,它会将该值设置为空字符串,并对原来的单词重新执行缩写查找。这确保了所有单词都有机会找到一个唯一的缩写,避免了数据的丢失。
🦆
在处理冲突的`add`函数中,一旦发现缩写`a`已经存在于`cache`中,为什么要将`cache[a]`设置为空字符串?这样做有什么具体的目的或好处?
将`cache[a]`设置为空字符串是为了标记这个缩写已经引起了冲突,不能被任何单词使用。这样做的具体好处是,它迫使代码重新为与此缩写冲突的所有单词寻找新的缩写,确保每个单词都能最终拥有一个独一无二的缩写。此外,这种方法也帮助避免了无限循环或重复处理同一个冲突。
🦆
函数`add`中使用了递归调用(`add(w2)`)来处理缩写冲突,这种递归调用可能存在哪些潜在的风险或效率问题?
递归调用`add(w2)`来处理冲突可能导致几个潜在的风险或效率问题:1. **栈溢出**:如果单词数量很多或冲突频繁发生,递归深度可能会变得很深,这可能导致栈溢出错误。2. **重复计算**:递归过程中可能多次处理同一单词,特别是当多个单词频繁冲突时,这会导致效率低下。3. **时间复杂度增加**:每次冲突发生时,都需要重新为单词找到一个新的缩写,这可能导致整个算法的时间复杂度大幅增加,尤其是在单词数目较多的情况下。

相关问题

有效单词缩写

有效单词缩写

最短独占单词缩写

最短独占单词缩写