LWC 63:748. Shortest Completing Word

LWC 63:748. Shortest Completing Word

传送门:748. Shortest Completing Word

Problem:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate Here, for letters we ignore case. For example, “P” on the licensePlate still matches “p” on the word. It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array. The license plate might have the same letter occurring multiple times. For example, given a licensePlate of “PP”, the word “pair” does not complete the licensePlate, but the word “supper” does.

Example 1:

Input: licensePlate = “1s3 PSt”, words = [“step”, “steps”, “stripe”, “stepple”] Output: “steps” Explanation: The smallest length word that contains the letters “S”, “P”, “S”, and “T”. Note that the answer is not “step”, because the letter “s” must occur in the word twice. Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

Input: licensePlate = “1s3 456”, words = [“looks”, “pest”, “stew”, “show”] Output: “pest” Explanation: There are 3 smallest length words that contains the letters “s”. We return the one that occurred first.

Note:

licensePlate will be a string with length in range [1, 7].

licensePlate will contain digits, spaces, or letters (uppercase or lowercase).

words will have a length in the range [10, 1000].

Every words[i] will consist of lowercase letters, and have length in range [1, 15].

思路: 很暴力,找到一个word符合licensePlate的定义,并不断更新即可。只要licensePlate中出现的字母,word中必须出现,且出现的次数至少相等。采用map计数。

Java版本:

    public String shortestCompletingWord(String licensePlate, String[] words) {
        String ans = "";
        int minLen = 1111;

        int[] map = new int[32];
        for (char c : licensePlate.toLowerCase().toCharArray())
            if (c >= 'a' && c <= 'z') map[c - 'a'] ++;


        for (String word : words) {
            int len = word.length();
            if (contains(map, word)) {
                if (len < minLen) {
                    ans = word;
                    minLen = len;
                }
            }
        }
        return ans;
    }

    boolean contains(int[] map, String word) {
        int[] map2 = new int[32];
        for (char c : word.toLowerCase().toCharArray()) {
            map2[c - 'a'] ++;
        }

        for (int i = 0; i < 32; ++i) {
            if (map[i] != 0) {
                if (map2[i] < map[i]) return false;
            }
        }
        return true;
    }

Python版本:

    def shortestCompletingWord(self, licensePlate, words):
        """
        :type licensePlate: str
        :type words: List[str]
        :rtype: str
        """
        licence_plate = licensePlate.lower()
        d = dict()
        for c in licence_plate:
            if c.isalpha():
                if c not in d:
                    d[c] = 0
                d[c] += 1

        res = None
        length = 1111
        for word in words:
            freq = d.copy()
            for c in word:
                if c in freq:
                    freq[c] -= 1
                    if freq[c] == 0:
                        freq.pop(c)
                if not freq:
                    if len(word) < length:
                        res = word
                        length = len(word)

        return res 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员宝库

如何用JavaScript手动实现一个栈

在生活中也能发现很多栈的例子。例如,厨房里堆放的盘子,总是叠在上方的先被使用;输入框内容进行删除时,总是最后输入的先删除;弹夹中的子弹,越后装入的,越先发射.....

1114
来自专栏java学习

重要通知!小编出新的Java练习题咯!!

正确答案 3月5号公布 一、选择题和问答题 1、在一个java原文件中,import, class, package语句的顺序是( )。 A. import ...

4105
来自专栏LeetCode

LeetCode 738. Monotone Increasing Digits

这是我开始选择的方法,非常直白,但是直白简单的方法往往不是最佳的解法,提交到LeetCode上,给我抛出一个超时,可见效率有多低。首先写一个函数,判断一个数是否...

1340
来自专栏XAI

程序员必知的8大排序(java实现)

8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

19910
来自专栏个人随笔

Java 关于集合框架那点事儿

 1.引入集合框架   采用数组存在的一些缺陷:    1.数组长度固定不变,不能很好地适应元素数量动态变化的情况。    2.可通过数组名.length获取数...

28710
来自专栏cmazxiaoma的架构师之路

Java数据结构和算法(2)--《Java数据结构和算法》第二版 Robert lafore第二章【数组】编码作业

2023
来自专栏恰同学骚年

数据结构基础温故-2.栈

现实生活中的事情往往都能总结归纳成一定的数据结构,例如餐馆中餐盘的堆叠和使用,羽毛球筒里装的羽毛球等都是典型的栈结构。而在.NET中,值类型在线程栈上进行分配,...

783
来自专栏从流域到海域

《数据结构》 定长顺序串常用操作代码集合

代码来自老师上课使用的ppt或者课本 /*定长顺序串*/ #define MAXLEN 40 typedef struct { char ch[M...

1956
来自专栏顶级程序员

判断链表是否有环

判断一个单向链表是否有环。(指向表头结点的指针为head) 方法一: (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head (2)p1和p2分别...

4587
来自专栏androidBlog

笔试题—字符串常见的算法题集锦

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

1121

扫码关注云+社区