通过删除字母匹配到字典里最长单词
删除 通过 匹配 字典 最长 单词 字母
2023-09-14 09:01:28 时间
524. 通过删除字母匹配到字典里最长单词
给你一个字符串 s 和一个字符串数组 dictionary ,找出并返回 dictionary 中最长的字符串,该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个,返回长度最长且字母序最小的字符串。如果答案不存在,则返回空字符串。
示例 1:
输入:s = “abpcplea”, dictionary = [“ale”,“apple”,“monkey”,“plea”]
输出:“apple”
示例 2:
输入:s = “abpcplea”, dictionary = [“a”,“b”,“c”]
输出:“a”
代码(java):
import java.util.Arrays;
import java.util.List;
public class longestWord {
public static void main(String[] args) {
// TODO 自动生成的方法存根
String s = "abpcplea";
String [] q = {"ale","apple","monkey","plea"};
List<String> dictionary = Arrays.asList(q) ;
String s1 = findLongestWord(s, dictionary);
System.out.println(s1);
}
public static String findLongestWord(String s, List<String> d) {
String longestWord = "";
for(String target : d) {
int l1 = longestWord.length(), l2 = target.length();
if(l1 > l2 || (l1 == l2 && longestWord.compareTo(target)<0)) {
continue;
}
if(isSubstr(s, target)) {
longestWord = target;
}
}
return longestWord;
}
private static boolean isSubstr(String s, String target) {
int i = 0, j = 0;
while(i < s.length() && j < target.length()) {
if(s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}
}
复杂度分析:
-
时间复杂度:O(d×(m+n)),其中 d表示dictionary 的长度,m 表示 s的长度,n 表示 dictionary 中字符串的平均长度。我们需要遍历dictionary 中的 d 个字符串,每个字符串需要O(n+m) 的时间复杂度来判断该字符串是否为 s 的子序列。
-
空间复杂度:O(1)。
提示:
- 1 <= s.length <= 1000
- 1 <= dictionary.length <= 1000
- 1 <= dictionary[i].length <= 1000
- s 和 dictionary[i] 仅由小写英文字母组成
来源:力扣(LeetCode)
注:仅供学习参考!
相关文章
- vim 删除临时文件
- ASP.NET关于书籍详情和删除的Demo(HttpHandler进行页面静态化[自动生成html网页]+Entity Framework通过类创建数据库+EF删查)...
- ASP.NET关于书籍详情和删除的Demo(HttpHandler进行页面静态化[自动生成html网页]+Entity Framework通过类创建数据库+EF删查)...
- Java实现 LeetCode 524 通过删除字母匹配到字典里最长单词(又是一道语文题)
- git 删除远程分支
- win10 新增、删除、重命名文件需要刷新才更新的问题
- Linux添加/删除用户和用户组
- 新浪面试题:删除字符串中多余的空格
- 已安装 SQL Server 2005 Express 工具。若要继续,请删除 SQL Server 2005 Express 工具
- vue.js 3.2.20:拖动创建div及移动、缩放、删除等操作
- centos8平台redis cluster集群添加/删除node节点(redis5.0.7)
- PCL 删除点云中重叠的点(方法二)
- JDBC的CRUD操作之PreparedStatement的删除操作
- 如何对 ABAP 数据库表通过 ABAP 代码进行更新和删除操作试读版
- C# 通过传入节点name及节点value,来删除XML相应节点
- C++里怎么样让类对象删除时自动释放动态分配的内存?
- docker 批量删除含有同样名字的images
- jQuery(三)添加/删除/替换/克隆元素、事件
- linux 脚本编写实战:通过账号列表文本快速添加和删除用户
- Mysql实战篇之可以通过删除记录来缩小表空间大小吗?--05