leetcode748-Shortest Completing Word

题目

给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。

补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。

例如：licensePlate = “aBc 12c”，那么它的补全词应当包含字母 ‘a’、‘b’ （忽略大写）和两个 ‘c’ 。可能的 补全词 有 “abccdef”、“caaacab” 以及 “cbca” 。
请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。
示例 1：
输入：licensePlate = “1s3 PSt”, words = [“step”, “steps”, “stripe”, “stepple”]
输出：“steps”
解释：最短补全词应该包括 “s”、“p”、“s”（忽略大小写） 以及 “t”。
“step” 包含 “t”、“p”，但只包含一个 “s”，所以它不符合条件。
“steps” 包含 “t”、“p” 和两个 “s”。
“stripe” 缺一个 “s”。
“stepple” 缺一个 “s”。
因此，“steps” 是唯一一个包含所有字母的单词，也是本例的答案。

分析

这道题目感觉纯粹是在考字符串的一些操作。字符可以直接转成数字的，我们先统计licensePlate中每个字母出行的次数，然后再遍历words依次统计每个字符串中字符出行的次数，如果相同字母下前者的次数比后者大，那么这个字符串就不是一个合法的字符串，与此同时遍历完所有的 words找到那个最短的即可

public class shortestCompletingWord {
public static void main(String[] args) {
String licensePlate = "1s3 PSt";
String[] words = {"step", "steps", "stripe", "stepple"};
System.out.println(getStr(licensePlate,words));
}
public static String getStr(String licensePlate, String[] words) {
int len = licensePlate.length();
int[] arr = new int[26];
for(int i = 0;i<len;i++) {
char c = licensePlate.charAt(i);
if(c >= 'a' && c <= 'z') {
arr[c - 'a']++;
}
if(c >= 'A' && c <= 'Z') {
arr[c - 'A']++;
}
}
String ret = "";
int min = Integer.MAX_VALUE;
for(String str : words) {
int strLen= str.length();
int[] brr = new int[26];
for(int i = 0;i<strLen;i++) {
char b = str.charAt(i);
if(b >= 'a' && b <= 'z') {
brr[b - 'a']++;
}
if(b >= 'A' && b <= 'Z') {
brr[b - 'A']++;
}
}
int tag = 0;
for(int i = 0;i<26;i++) {
if(arr[i] > brr[i]) {
tag = 1;
}
}
if(tag == 0 && min > strLen) {
min = strLen;
ret = str;
}
}
return ret;
}
}

原文地址：https://blog.csdn.net/wellwang1993/article/details/137892007

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！