跳至正文

每日一题——748. 最短补全词

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语句写完却完全没有排列,不知道是哪出了问题

发表评论

您的电子邮箱地址不会被公开。