LeetCode算法题-Shortest Completing Word(Java实现)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法题-Shortest Completing Word(Java实现),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3495字,纯文字阅读大概需要5分钟。
内容图文
![LeetCode算法题-Shortest Completing Word(Java实现)](/upload/InfoBanner/zyjiaocheng/832/376b72399f574d1b8853be6253f8ed29.jpg)
这是悦乐书的第309次更新,第330篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第178题(顺位题号是748)。从给定的字典单词中查找最小长度单词,其中包含字符串licensePlate中的所有字母。据说这样的单词可以完成给定的字符串licensePlate。在这里,对于字母我们忽略大小写。例如,licensePlate上的“P”仍与单词上的“p”匹配。答案肯定存在。如果有多个答案,则返回数组中首先出现的答案。licensePlate可能会多次出现相同的字母。例如,给定licensePlate为“PP”,单词“pair”不会完成licensePlate,但单词“supper”会完成。例如:
输入:licensePlate =“1s3 PSt”,words = [“step”,“steps”,“stripe”,“stepple”]
输出:“steps”
说明:包含字母“S”,“P”,“S”和“T”的最小长度字。请注意,答案不是“step”,因为字母“s”必须出现在单词中两次。另请注意,为了比较单词中是否存在字母,我们忽略了大小写。
输入:licensePlate =“1s3 456”,words = [“look”,“pest”,“stew”,“show”]
输出:“pest”
说明:有3个最小长度的单词,包含字母“s”。我们返回先出现的那个。
注意:
licensePlate将是一个长度在[1,7]范围内的字符串。
licensePlate将包含数字,空格或字母(大写或小写)。
数组的长度范围为[10,1000]。
每个words[i]将由小写字母组成,并且长度在[1,15]范围内。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
给定的licensePlate中包含数字、空格或大写字母,而比较时是忽略大小写的,所以我们先将licensePlate中的字母抽出来,并且将里面的大写字母转为小写,变成一个新的字符串。然后开始遍历words数组,比较数组的当前元素和前面得到的新字符串的关系,判断此单词是否能够由新字符串组成,在此将判断的方法独立处理,判断的方法是借助容量为26的整数数组,新字符串中有的字母,此单词中必须要有,否则就返回false。
public String shortestCompletingWord(String licensePlate, String[] words) {
String s = "";
for (char ch : licensePlate.toCharArray()) {
if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
s += ch;
}
}
s = s.toLowerCase();
String res = "";
for (String str : words) {
if ((res.isEmpty() || res.length() > str.length()) && isContains(s, str)) {
res = str;
}
}
return res;
}
/**
* 判断此单词是否全部包含新字符串中的字母
* @param s licensePlate中英文字母组成的字符串
* @param s2 words中的每个单词
* @return
*/
public boolean isContains(String s, String s2) {
int[] arr = new int[26];
// 将单词中的字母出现次数记数
for (char ch : s2.toCharArray()) {
arr[ch-'a']++;
}
for (char ch : s.toCharArray()) {
// 新字符串中的当前字母在单词中不存在
if (arr[ch-'a'] == 0) {
return false;
}
arr[ch-'a']--;
}
return true;
}
03 第二种解法
我们也可以将辅助方法融合到主方法中去。依旧是先将licensePlate里的字母抽出来,存入一个容量26的数组中,此处多使用了一个变量来记录新字符串中字母的总数量。然后开始循环处理words中的元素,每次循环都需要将数组和总数量复制一份,然后去做判断,判断的逻辑和上面第一种解法的思路类似。
public String shortestCompletingWord2(String licensePlate, String[] words) {
int[] arr = new int[26];
int count = 0;
for (char ch : licensePlate.toCharArray()) {
if (ch >= 'a' && ch <= 'z') {
arr[ch-'a']++;
count++;
} else if(ch >= 'A' && ch <= 'Z') {
arr[ch-'A']++;
count++;
}
}
String result = "";
for (String str : words) {
int temp = count;
int[] copy = arr.clone();
for (char ch : str.toCharArray()) {
if (--copy[ch-'a'] >= 0) {
temp--;
}
}
if (temp == 0 && (result.isEmpty() || result.length() > str.length())) {
result = str;
}
}
return result;
}
04 小结
算法专题目前已日更超过五个月,算法题文章178+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
内容总结
以上是互联网集市为您收集整理的LeetCode算法题-Shortest Completing Word(Java实现)全部内容,希望文章能够帮你解决LeetCode算法题-Shortest Completing Word(Java实现)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。