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 条评论
登录 后参与评论

相关文章

来自专栏FD的专栏

Effective Testing with RSpec 3 (英文版)(序言)

Early praise for Effective Testing with RSpec 3

1844
来自专栏CodingToDie

Awesome 项目

4165
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

812
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1462
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1182
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2702
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1162
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1866
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

471
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7965

扫码关注云+社区