0748. 最短补全词【简单】

1. 📝 题目描述
2. 🎯 s.1 - 暴力解法

1. 📝 题目描述

leetcode

给你一个字符串 licensePlate 和一个字符串数组 words，请你找出 words 中的最短补全词。

补全词是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的数字和空格。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。

例如：licensePlate = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c'。可能的补全词有 "abccdef"、"caaacab" 以及 "cbca"。

请返回 words 中的最短补全词。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中第一个出现的那个。

示例 1：

输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出："steps"
解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。
"step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。
"steps" 包含 "t"、"p" 和两个 "s"。
"stripe" 缺一个 "s"。
"stepple" 缺一个 "s"。
因此，"steps" 是唯一一个包含所有字母的单词，也是本例的答案。

示例 2：

txt

输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
输出："pest"
解释：licensePlate 只包含字母 "s"。所有的单词都包含字母 "s"，其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest"，因为它是三个单词中在 words 里最靠前的那个。

提示：

1 <= licensePlate.length <= 7
licensePlate 由数字、大小写字母或空格 ' ' 组成
1 <= words.length <= 1000
1 <= words[i].length <= 15
words[i] 由小写英文字母组成

2. 🎯 s.1 - 暴力解法

js（array）js（map）

/**
 * @param {string} licensePlate
 * @param {string[]} words
 * @return {string}
 */
var shortestCompletingWord = function (licensePlate, words) {
  // 统计 licensePlate 中字母出现次数
  const licenseCount = getCount(licensePlate)

  let result = ''

  // 遍历 words 数组查找最短补全词
  for (const word of words) {
    const wordCount = getCount(word)

    // 检查 word 是否包含 licensePlate 中所有字母且数量足够
    if (isCompletingWord(licenseCount, wordCount)) {
      // 更新最短补全词
      if (!result || word.length < result.length) {
        result = word
      }
    }
  }

  return result
}

// 统计字符串中字母出现次数（忽略大小写）
function getCount(str) {
  const count = new Array(26).fill(0)
  for (const char of str) {
    if (/[a-zA-Z]/.test(char)) {
      const index = char.toLowerCase().charCodeAt(0) - 'a'.charCodeAt(0)
      count[index]++
    }
  }
  return count
}

// 检查 word 是否是 license 的补全词
function isCompletingWord(licenseCount, wordCount) {
  for (let i = 0; i < 26; i++) {
    if (licenseCount[i] > wordCount[i]) {
      return false
    }
  }
  return true
}

/**
 * @param {string} licensePlate
 * @param {string[]} words
 * @return {string}
 */
var shortestCompletingWord = function (licensePlate, words) {
  // 使用哈希表统计 licensePlate 中字母出现次数
  const licenseCount = getCountWithMap(licensePlate)

  let result = ''

  // 遍历 words 数组查找最短补全词
  for (const word of words) {
    const wordCount = getCountWithMap(word)

    // 检查 word 是否包含 licensePlate 中所有字母且数量足够
    if (isCompletingWordWithMap(licenseCount, wordCount)) {
      // 更新最短补全词
      if (!result || word.length < result.length) {
        result = word
      }
    }
  }

  return result
}

// 使用哈希表统计字符串中字母出现次数（忽略大小写）
function getCountWithMap(str) {
  const count = new Map()
  for (const char of str) {
    if (/[a-zA-Z]/.test(char)) {
      const lowerChar = char.toLowerCase()
      count.set(lowerChar, (count.get(lowerChar) || 0) + 1)
    }
  }
  return count
}

// 使用哈希表检查 word 是否是 license 的补全词
function isCompletingWordWithMap(licenseCount, wordCount) {
  for (const [char, neededCount] of licenseCount) {
    if ((wordCount.get(char) || 0) < neededCount) {
      return false
    }
  }
  return true
}

时间复杂度： $O (N + M)$ ，其中 N 是 licensePlate 的长度，M 是所有 words 的长度总和
空间复杂度： $O (1)$ ，只使用了固定大小的数组（26 个字母）

0748. 最短补全词【简单】

0748. 最短补全词【简单】 ​

1. 📝 题目描述 ​

2. 🎯 s.1 - 暴力解法 ​

Discussions

0748. 最短补全词【简单】

1. 📝 题目描述

2. 🎯 s.1 - 暴力解法