LWC 57:720. Longest Word in Dictionary

LWC 57:720. Longest Word in Dictionary

传送门:720. Longest Word in Dictionary

Problem:

Given a list of strings words representing an English Dictionary, find 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.

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”.

Note:

All the strings in the input will only contain lowercase letters.

The length of words will be in the range [1, 1000].

The length of words[i] will be in the range [1, 30].

思路: 对于候选的答案如”apple”,从字典集中找出”a”,”ap”,”app”,”appl”,如果均能找到则进行最大长度的比较。为了长度最大,且字典序最小,当遇到相同字符串长度时,还需要再比较一次字符大小。

代码如下:

    public String longestWord(String[] words) {
        int n = words.length;
        Set<String> set = new HashSet<>();
        set.add("");
        for (int i = 0; i < n; ++i){
            set.add(words[i]);
        }
        String ans = "";
        int maxLen = 0;
        for (int i = 0; i < n; ++i){
            String word = words[i];
            if (valid(word, set)){
                int len = word.length();
                if (len >= maxLen){
                    if (len == maxLen){
                        if (ans.compareTo(word) > 0){
                            ans = word;
                        }
                    }
                    else{
                        ans = word;
                    }
                    maxLen = len;
                }
            }            
        }
        return ans;
    }

    boolean valid(String word, Set<String> set){
        int n = word.length();
        for (int i = 0; i < n; ++i){
            if (!set.contains(word.substring(0, i))) return false;
        }
        return true;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习入门

LWC 54:696. Count Binary Substrings

LWC 54:696. Count Binary Substrings 传送门:696. Count Binary Substrings Problem: G...

1727
来自专栏技术记录

java获取properties配置文件值

package me.ilt.Blog.util; import java.io.File; import java.io.FileInputStream; ...

1775
来自专栏Bingo的深度学习杂货店

Q771 Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S r...

2874
来自专栏calmound

UVA Hangman Judge

英语太烂啊。 In ``Hangman Judge,'' you are to write a program that judges a series of ...

3107
来自专栏ml

HDUOJ--2079选课时间(题目已修改,注意读题)

选课时间(题目已修改,注意读题) Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/3...

3326
来自专栏海说

Dubbo源码学习--服务发布(ProxyFactory、Invoker)

上文分析了Dubbo服务发布的整体流程,但服务代理生成的具体细节介绍得还不是很详细。下面将会接着上文继续分析。上文介绍了服务代理生成的切入点,如下: Invok...

7080
来自专栏King_3的技术专栏

leetcode-443-String Compression

1526
来自专栏pangguoming

MyBatis动态SQL foreach标签实现批量插入

需求:查出给定id的记录: <select id="getEmpsByConditionForeach" resultType="com.test.beans....

4823
来自专栏计算机视觉与深度学习基础

Leetcode 25 Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return ...

1839
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串,贪心+排序】

Balala Power! Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131...

2715

扫码关注云+社区