方法一:统计
统计licensePlate每个字母出现的频率、words数组中每个字符串中每个字母出现的次数,进行比较。
这个统计次数当然可以Map结构来统计,但是更方便的是用数组,数组的下标代表字母,值代表这个字母出现的次数。
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] freq = new int[26];
for (int i = 0; i < licensePlate.length(); i++) {
Character ch = licensePlate.charAt(i);
if (ch >= 'a' && ch <= 'z') {
freq[ch - 'a']++;
}
if (ch >= 'A' && ch <= 'Z') {
freq[ch - 'A']++;
}
}
int idx = -1;
for (int i = 0; i < words.length; i++) {
String str = words[i];
boolean flag = true;
int[] tmp = new int[26];
for (int j = 0; j < str.length(); j++) {
Character ch = str.charAt(j);
if (ch >= 'a' && ch <= 'z') {
tmp[ch - 'a']++;
}
if (ch >= 'A' && ch <= 'Z') {
tmp[ch - 'A']++;
}
}
for (int j = 0; j < 26; j++) {
if (freq[j] > tmp[j]) {
flag = false;
break;
}
}
if (flag) {
if (idx < 0 || words[idx].length() > words[i].length()) {
idx = i;
}
}
}
return words[idx];
}
}