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 条评论
登录 后参与评论

相关文章

来自专栏飞扬的花生

SqlServer批量刷数据执行事务回滚语句备份

      企业进行对数据库执行刷数据工作,一段很长的语句希望同时成功或者失败时用到。 1.建立测试环境 /**************************...

2006
来自专栏用户2442861的专栏

mysql索引index相关命令

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

792
来自专栏源哥的专栏

一个用来生成流水号的存储过程

我们经常需要用一个流水号来唯一表示一条数据,我们有时采用队列来自动生成一个唯一的流水号,但是采用队列经常不能满足我们的需求,比如说,这个队列只能设定一个最小值,...

581
来自专栏数据结构与算法

Kosaraju算法详解

Kosaraju算法可以求出有向图中的强连通分量个数,并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单: (1) 第一次对图G进行DFS遍历,并在...

3366
来自专栏Jerry的SAP技术分享

ABAP OPEN SQL里OPEN CURSOR和SELECT的比较

After the OPEN CURSOR statement, the database cursor is positioned in front of t...

3589
来自专栏数据和云

突破常识:SQL增加DISTINCT后查询效率反而提高

杨廷琨,网名 yangtingkun 云和恩墨技术总监,Oracle ACE Director,ACOUG 核心专家 只要增加了DISTINCT关键字,Orac...

2946
来自专栏Bingo的深度学习杂货店

Q1 Two Sum

Given an array of integers, return indices of the two numbers such that they add...

2756
来自专栏来自地球男人的部落格

[LeetCode] 137. Single Number II

【原题】 Given an array of integers, every element appears three times except for...

17610
来自专栏杨建荣的学习笔记

生产环境sql语句调优实战第四篇(r2笔记41天)

生产中有一条sql语句消耗了大量的cpu资源,执行时间在18秒左右, Session:PRODBUSER (1560:61133)SQL ID:1hg2wcua...

2045
来自专栏pangguoming

SQL语句大小写是否区分的问题,批量修改整个数据库所有表所有字段大小写

一、实例介绍 SQL语句大小写到底是否区分呢?我们先从下面的这个例子来看一下: 例: --> 创建表,插入数据: declare @maco table (nu...

3587

扫码关注云+社区