748. 最短补全词
给你一个字符串 licensePlate 和一个字符串数组 words ,请你找出并返回 words 中的 最短补全词 。
补全词 是一个包含 licensePlate 中所有的字母的单词。在所有补全词中,最短的那个就是 最短补全词 。
在匹配 licensePlate 中的字母时:
忽略 licensePlate 中的 数字和空格 。
不区分大小写。
如果某个字母在 licensePlate 中出现不止一次,那么该字母在补全词中的出现次数应当一致或者更多。
例如:licensePlate = “aBc 12c”,那么它的补全词应当包含字母 ‘a’、’b’ (忽略大写)和两个 ‘c’ 。可能的 补全词 有 “abccdef”、”caaacab” 以及 “cbca” 。
请你找出并返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 最靠前的 那个。
public class Solution { public string ShortestCompletingWord(string licensePlate, string[] words) { //和383.赎金信类似的字符串遍历和比较的方法 int[] cnt = new int[26]; foreach (char c in licensePlate) { //先做大小写的转换,如果是大写的先转成小写 //这里用的是char.ToLower方法 if(char.IsLetter(c)) { cnt[char.ToLower(c) - 'a']++; } } int index = -1; //words = words.OrderBy(s => s.Length).ToArray(); for(int i=0;i<words.Length;i++) { int[] temp = new int[26]; //依次遍历字符串数组里的每一个字符串 foreach(char c in words[i]) { temp[c - 'a']++; } bool fine = true; for(int j=0;j<26;j++) { if(cnt[j] > temp[j]) { fine = false; break; } } if(fine&&(index <0 || words[i].Length < words[index].Length)) { index = i; } } return words[index]; } }
这道题跟383.赎金信这道题很像
同样是涉及到两个字符串比较
不过这题会比较特殊一点
两个迭代器和两个数组
数组存放对应26个字母出现的次数
如果licensePlate对应的字母出现次数比这个字符串对应的来得大
证明这个字符串不行
遍历这个字符串数组后记录长度最短的索引
输出就完事了
顺便一提这道题我本以为用linq按长度顺序排列字符串数组会更好
发现linq语句写完却完全没有排列,不知道是哪出了问题