首页 > 其他分享 >LeetCode 720. Longest Word in Dictionary

LeetCode 720. Longest Word in Dictionary

时间:2024-06-03 12:54:38浏览次数:22  
标签:word Dictionary res return length words visited Word LeetCode

原题链接在这里:https://leetcode.com/problems/longest-word-in-dictionary/description/

题目:

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Note that the word should be built from left to right with each additional character being added to the end of a previous word. 

Example 1:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Constraints:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 30
  • words[i] consists of lowercase English letters.

题解:

Sort the words, then with the same prefix, longer words will come after shorter words.

Iterate the words, for current word, if its prefix already exist in the visited set, we can add it to the visited set and update the result.

Time Complexity: O(nlogn + n * len). n = words.length. len is the length of longest length of word.

Space: O(n * len).

AC Java:

 1 class Solution {
 2     public String longestWord(String[] words) {
 3         String res = "";
 4         if(words == null || words.length == 0){
 5             return res;
 6         }
 7         
 8         Arrays.sort(words);
 9         HashSet<String> visited = new HashSet<>();
10         for(String w : words){
11             if(w.length() == 1 || visited.contains(w.substring(0, w.length() - 1))){
12                 visited.add(w);
13                 if(w.length() > res.length()){
14                     res = w;
15                 }
16             }
17         }
18         
19         return res;
20     }
21 }

 

标签:word,Dictionary,res,return,length,words,visited,Word,LeetCode
From: https://www.cnblogs.com/Dylan-Java-NYC/p/18228621

相关文章

  • leetcode第263题:丑数
    丑数的因子只能是2,3,5。但是可能有多个2,多个3,多个5.因此需要循环地除以2、3、5.publicclassSolution{publicboolIsUgly(intn){if(n<=0){returnfalse;}int[]factors={2,3,5};for(inti=0;i......
  • leetcode第1281题: 整数的各位积和之差
    publicclassSolution{publicintSubtractProductAndSum(intn){intsum=0;intji=1;while(n>0){intnum=n%10;sum+=num;ji*=num;n/=10;}returnji-sum;......
  • LeetCode 1151. 最少交换次数来组合所有的 1
    1151.最少交换次数来组合所有的1给出一个二进制数组 data,你需要通过交换位置,将数组中 任何位置 上的1组合到一起,并返回所有可能中所需 最少的交换次数。示例1:输入:data=[1,0,1,0,1]输出:1解释:有三种可能的方法可以把所有的1组合在一起:[1,1,1,0,0],交换......
  • LeetCode 1411. Number of Ways to Paint N × 3 Grid
    原题链接在这里:https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/description/题目:Youhavea grid ofsize nx3 andyouwanttopainteachcellofthegridwithexactlyoneofthethreecolors: Red, Yellow, or Green whilemakingsuretha......
  • leetcode 60 排列序列
    排列序列已解答困难相关标签相关企业给出集合[1,2,3,...,n],其所有元素共有n!种排列。按大小顺序列出所有排列情况,并一一标记,当n=3时,所有排列如下:"123""132""213""231""312""321"给定n和k,返回第k个排列。示例1:输入:n=3,k=3输出:"213"示......
  • Leetcode 3171. Find Subarray With Bitwise AND Closest to K
    Leetcode3171.FindSubarrayWithBitwiseANDClosesttoK1.解题思路2.代码实现题目链接:3171.FindSubarrayWithBitwiseANDClosesttoK1.解题思路这道题坦率地说让我感觉很挫败,又一次没有自力搞定,是看了大佬们的答案才搞定的……知道比没有搞定更难受的......
  • wordpress搭建博客
    前排提醒由于本人的服务器只有1G内存,但是mysql启动就占用500M,系统占用500M,导致wordpress计划流产。Abstract本文将记录本人使用wordpress搭建博客的流程。0.Requirements系统:Ubuntu22.04根据wordpress官网指引,需要如下软件支持:PHPversion7.4orgreater.MySQLversio......
  • leetcode-280. 摆动数组
    给你一个的整数数组nums,将该数组重新排序后使nums[0]<=nums[1]>=nums[2]<=nums[3]...简单想法排序双指针,一前一后插入贪心?猜的假定前i个已经摆动,i+1存在奇、偶两种情况奇数——若nums[i+1]>=nums[i+2]则符合条件,若nums[i+1]<nums[i+2],尝试交换......
  • LeetCode //C - 147. Insertion Sort List
    147.InsertionSortListGiventheheadofasinglylinkedlist,sortthelistusinginsertionsort,andreturnthesortedlist’shead.Thestepsoftheinsertionsortalgorithm:Insertionsortiterates,consumingoneinputelementeachrepetitionand......
  • leetcode-624.数组列表中的最大距离
    数组列表中的最大距离给定m个数组,每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数(每个数组选一个)并且计算它们的距离。两个整数a和b之间的距离定义为它们差的绝对值|a-b|。你的任务就是去找到最大距离目标题意中的绝对值|a-b|等价于选取......