首页 > 其他分享 >LeetCode题练习与总结:连接词--472

LeetCode题练习与总结:连接词--472

时间:2024-12-16 15:32:43浏览次数:10  
标签:单词 -- 复杂度 472 连接词 words 集合 dp

一、题目描述

给你一个 不含重复 单词的字符串数组 words ,请你找出并返回 words 中的所有 连接词 。

连接词 定义为:一个完全由给定数组中的至少两个较短单词(不一定是不同的两个单词)组成的字符串。

示例 1:

输入:words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出:["catsdogcats","dogcatsdog","ratcatdogcat"]
解释:"catsdogcats" 由 "cats", "dog" 和 "cats" 组成; 
     "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成; 
     "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。

示例 2:

输入:words = ["cat","dog","catdog"]
输出:["catdog"]

提示:

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 30
  • words[i] 仅由小写英文字母组成。 
  • words 中的所有字符串都是 唯一 的。
  • 1 <= sum(words[i].length) <= 10^5

二、解题思路

  1. 首先,对单词数组按照单词长度进行排序。这样可以确保我们在检查一个单词是否为连接词时,所有可能的组成单词都已经在集合中了。
  2. 使用一个集合来存储已经遍历过的单词,这样可以在常数时间内检查一个单词是否为连接词。
  3. 对于每个单词,使用深度优先搜索(DFS)或动态规划(DP)来检查它是否可以由至少两个更短的单词组成。
  4. 如果一个单词是连接词,则将其添加到结果列表中。

三、具体代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        // 按单词长度排序
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Set<String> wordSet = new HashSet<>();
        List<String> result = new ArrayList<>();

        for (String word : words) {
            // 检查当前单词是否为连接词
            if (isConcatenatedWord(word, wordSet)) {
                result.add(word);
            }
            // 将当前单词加入集合,供后续单词检查使用
            wordSet.add(word);
        }

        return result;
    }

    private boolean isConcatenatedWord(String word, Set<String> wordSet) {
        if (wordSet.isEmpty()) {
            return false;
        }
        int n = word.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // 如果当前子串在集合中,并且前面的子串可以由集合中的单词组成
                if (dp[j] && wordSet.contains(word.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        // 必须由至少两个单词组成
        return dp[n] && n != wordSet.stream().filter(w -> w.equals(word)).mapToInt(String::length).findFirst().orElse(0);
    }
}

在这个实现中,我们首先按照单词长度对单词数组进行排序,然后使用动态规划来判断每个单词是否是连接词。isConcatenatedWord 方法中,dp[i] 表示字符串 word 的前 i 个字符是否可以由集合 wordSet 中的单词组成。我们检查每个可能的子串,如果它存在于集合中,并且之前的子串可以由集合中的单词组成,那么 dp[i] 被设置为 true

此外,为了避免将单个单词错误地标记为连接词,我们确保了连接词至少由两个单词组成,这通过检查 dp[n] 为 true 且单词长度不等于它在集合中的长度来实现。

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 排序单词数组:排序的时间复杂度为 O(n log n),其中 n 是单词的数量。

  • 遍历单词数组并检查每个单词是否为连接词:对于每个单词,我们需要进行动态规划。动态规划的时间复杂度为 O(m^2),其中 m 是单词的长度。因此,对于所有单词的总时间复杂度为 O(n * m^2)。

  • isConcatenatedWord 方法中的 wordSet.contains 操作在哈希集合中平均是 O(1) 的时间复杂度。但是,对于每个单词,我们需要检查所有可能的子串,这会导致 O(m^2) 的操作。

综合以上,总的时间复杂度为 O(n log n + n * m^2),其中 n 是单词的数量,m 是单词的平均长度。

2. 空间复杂度
  • 哈希集合 wordSet 用来存储所有单词,其空间复杂度为 O(n * m),其中 n 是单词的数量,m 是单词的平均长度。

  • 动态规划数组 dp 的空间复杂度为 O(m),其中 m 是单词的长度。

  • 递归调用栈的深度在 isConcatenatedWord 方法中最多为 m,因此递归栈的空间复杂度为 O(m)。

综合以上,总的空间复杂度为 O(n * m + m + m),简化后为 O(n * m),其中 n 是单词的数量,m 是单词的平均长度。

五、总结知识点

  • Java 集合框架

    • ArrayList:用于存储结果列表。
    • HashSet:用于存储单词集合,以便进行快速的查找操作。
    • List 和 Set 接口:分别表示列表和集合的抽象数据类型。
  • Java 数组

    • boolean[] dp:使用布尔数组来实现动态规划,存储子问题的解。
  • Java 8 特性

    • Stream API:在检查连接词时,使用 stream().filter().mapToInt().findFirst().orElse() 来找到集合中与当前单词相同长度的单词(这一部分实际上是不必要的,因为 dp[n] 已经足够判断单词是否是连接词)。
  • 排序

    • Arrays.sort:对字符串数组进行排序,这里使用了 lambda 表达式来定义比较器。
  • 字符串操作

    • String.substring:用于获取字符串的子串。
  • 动态规划

    • 使用动态规划(DP)来判断一个单词是否可以由集合中的其他单词组成。dp[i] 表示字符串的前 i 个字符是否可以由集合中的单词组成。
  • 递归与迭代

    • 在 isConcatenatedWord 方法中,通过迭代而不是递归来实现动态规划。
  • 逻辑判断

    • 代码中包含了多个 if 语句,用于进行条件判断。
  • 面向对象编程

    • Solution 类的定义和使用,以及 findAllConcatenatedWordsInADict 和 isConcatenatedWord 方法的定义,体现了面向对象编程的思想。
  • 方法重载与封装

    • isConcatenatedWord 方法被封装为私有方法,仅在其所在的类内部使用,这体现了封装的原则。
  • 算法设计

    • 整体算法设计包括排序、集合查找、动态规划等,体现了算法设计的基本思路。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

标签:单词,--,复杂度,472,连接词,words,集合,dp
From: https://blog.csdn.net/weixin_62860386/article/details/144494897

相关文章

  • LeetCode题练习与总结:火柴拼正方形--473
    一、题目描述你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒,但你可以把它们连在一起,而且每根火柴棒必须 使用一次 。如果你能使这个正方形,则返回 true ,否则返......
  • 如何在 Spring Boot 应用程序中使用 WireMock 模拟外部 rest api 调用进行测试
    模拟外部API调用是集成或端到端测试中的常见做法,因为它允许开发人员将他们的代码与外部隔离。如果我们使用付费API并希望避免在测试时进行调用以节省资金,这也会有所帮助。有两种方法可以模拟外部API使用Mockito使用WireMock在集成测试和端到端测试中,我更喜欢使用Wir......
  • 接口数据做缓存,响应飞快似天神
    概述在商业中“现金为王”,而在互联网整个软件世界中,有一个与之相近的说法是“缓存为王”。本文我们重点说明缓存方向:将方法的返回值缓存起来,下次再调用该方法时,如果方法的参数与之前调用时的参数相同,则会直接返回缓存中的结果,而不会再执行方法体。这样可以提高方法的执......
  • WEB集群--HTTP协议
    HTTP概述默认端口:80HTTP(超文本传输协议):数据请求与响应请求request:访问网站响应response:显示网站,返回客户端想要的内容#curl-vwww.baidu.com#wget--debugwww.baidu.com---requestbegin---GET/HTTP/1.1User-Agent:Wget/1.14(linux-gnu)Accept:*/*Host:b......
  • JavaScript的对象相关概念
    当然可以,以下是将上述对话整理成Markdown格式的内容:JavaScript面向对象编程相关概念原型链(PrototypeChain)原型链是JavaScript中查找对象属性和方法的机制。它从对象的__proto__属性开始,向上逐层搜索直到找到属性或方法或到达Object.prototype。原型(Prototype)每个Java......
  • Spring Cloud 面试锦集
    2020-SpringCloud面试锦集一:什么是微服务架构?二:Ribbon?1:负载均衡的核心组件?2:负载均衡算法?3:负载均衡的替换?4:Ribbon轮询负载均衡算法?三:Springcloud和springboot版本依赖关系四:eureka?五:openFeign六:Hystrix一:什么是微服务架构?微服务架构是一种架构模式,他提倡......
  • 使用wsimport命令生成webService客户端代码
    wsimport 是JDK自带的一个工具,可以根据WSDL文件生成Java类。1.进入JDK/bin目录,从地址栏进入cmd 2.执行如下命令:wsimport-keep-sD:\tmp-pcom.cn.phone-verbosehttp://ws.webxml.com.cn/WebServices/MobileCodeWS.asmx?wsdl-keep:是否生成java源文件-s:指定.ja......
  • 闲置物品交易平台-毕业设计源码04508
    摘要本项目旨在基于SSM框架开发一款闲置物品交易平台,为用户提供一个便捷、安全的平台,实现用户间的二手物品交易和共享。该平台将包括用户管理、商品管理、交易管理和支付管理等模块,通过前端页面设计和后端技术的结合,为用户提供良好的交易体验和安全保障。用户可以注册账......
  • (附源码)springboot高校大学生就业管理信息系统-计算机毕设 33061
    高校大学生就业管理信息系统设计与实现摘 要在网络飞速发展的信息时代,各个行业都离不开信息的处理,在这种时代背景下,学校以学生的信息管理为导向,根据这点,为当前形势最重要的高校大学生就业管理信息设计一个就业信息管理系统就很有必要。高校大学生高校大学生就业管理信......
  • 呕心沥血上万字——详解 TCP 协议!!
    目录1.TCP协议特点2.TCP报文格式 2.1源端口/目的端口2.24位首部长度2.3选项2.4保留位2.516位校验和2.66位标志位3.TCP核心机制一:确认应答3.1先发后至3.2序号/确认序号3.2.1如何编排3.2.2排序4.TCP核心机制二:超时重传4.1丢包 4.1.1丢......