>720. 词典中最长的单词<

>longestWord<

定义「符合要求的单词」如下：

▶空字符串是符合要求的单词；

▶在符合要求的单词的末尾添加一个字母，得到的新单词是符合要求的单词。

字典序：即是英文字母表的顺序

Arrays.sort()方法

根据指定比较器产生的顺序对指定对象数组进行排序。数组中的所有元素都必须是通过指定比较器可相互比较的（也就是说，对于数组中的任何 e1 和 e2 元素而言，c.compare(e1, e2) 不得抛出 ClassCastException）。

public static <T> void sort(T[] a,Comparator<? super T> c)

对一维数组进行排序

直接使用 Arrays.sort(arr)，默认是升序排序。

对二维数组进行排序

1. 按照 arr 数组中的每一行的第一列进行比较，并按照升序排序。

 Arrays.sort(arr, (a, b) -> a[0] - b[0]);

2. 按照 arr 数组中的每一行的第一列进行比较，并按照降序排序。

 Arrays.sort(arr, (a, b) -> b[0] - a[0]);

substring()方法

public String substring(int beginIndex,int endIndex)"hamburger".substring(4, 8) returns "urge" "smiles".substring(1, 5) returns "mile"

返回一个新字符串，它是此字符串的一个子字符串。该子字符串从指定的 beginIndex 处开始，直到索引 endIndex - 1 处的字符。因此，该子字符串的长度为 endIndex-beginIndex。
▶参数简介：
beginIndex - 起始索引（包括）。
endIndex - 结束索引（不包括）。

一、解题思路

1、解法一( Java )

解法思路：HashSet哈希集合

这道题要求返回数组中的最长的符合要求的单词，如果有多个最长的符合要求的单词则返回其中字典序最小的单词。

需要将数组 words 排序，排序的规则是首先按照单词的长度升序排序，如果单词的长度相同则按照字典序降序排序。排序之后，可以确保当遍历到每个单词时，比该单词短的全部单词都已经遍历过，且每次遇到符合要求的单词一定是最长且字典序最小的单词，可以直接更新答案。

将答案初始化为空字符串。使用哈希集合存储所有符合要求的单词，初始时将空字符串加入哈希集合。遍历数组 words，对于每个单词，判断当前单词去掉最后一个字母之后的前缀是否在哈希集合中，如果该前缀在哈希集合中则当前单词是符合要求的单词，将当前单词加入哈希集合，并将答案更新为当前单词。

遍历结束之后，返回答案。

伪代码如下：

class Solution {    public String longestWord(String[] words) { Arrays.sort(words, (a, b) -> {     if (a.length() != b.length()) {  return a.length() - b.length();     } else {  return b.compareTo(a);     } }); String res = ""; Set<String> set = new HashSet<String>(); set.add(""); int len = words.length; for (int i = 0; i < len; i++) {     String word = words[i];     if (set.contains(word.substring(0, word.length() - 1))) {  set.add(word);  res = word;     } } return res;    }}

完整代码如下：

package daily_leetcode;import java.util.Arrays;import java.util.HashSet;import java.util.Set;/** * @author Listen 1024 * @date 2022-03-17 9:58 */public class 词典中最长的单词_720 {    public static void main(String[] args) { String[] strings = new String[]{"a", "banana", "app", "appl", "ap", "apply", "apple"}; Solution index = new Solution(); String resString = index.longestWord(strings); System.out.println(resString);    }}class Solution {    public String longestWord(String[] words) { Arrays.sort(words, (a, b) -> {     if (a.length() != b.length()) {  return a.length() - b.length();//按照单词的长度升序排序(返回值大于0时b在前a在后，返回值小于0时a在前b在后)     } else {  return b.compareTo(a);//单词的长度相同时则按照字典序降序排序(返回值大于0时b在前a在后，返回值小于0时a在前b在后)     } }); String res = "";//将答案初始化为空字符串 Set<String> set = new HashSet<String>();//使用哈希集合存储所有符合要求的单词 set.add("");//初始时将空字符串加入哈希集合 int len = words.length; for (int i = 0; i < len; i++) {     String word = words[i];     if (set.contains(word.substring(0, word.length() - 1))) {//判断当前单词去掉最后一个字母之后的前缀是否在哈希集合中  set.add(word);//如果该前缀在哈希集合中则当前单词是符合要求的单词，将当前单词加入哈希集合，并将答案更新为当前单词。  res = word;     } } return res;//返回答案    }}

运行结果截图如下：

艺术系歌词下载吧