每日一题---748. 最短补全词[力扣][Go]-阿里云开发者社区

每日一题---748. 最短补全词[力扣][Go]

2023-02-23 94

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 每日一题---748. 最短补全词[力扣][Go]

题目描述

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

补全词是一个包含 licensePlate 中所有的字母的单词。在所有补全词中，最短的那个就是最短补全词。

在匹配 licensePlate 中的字母时：

忽略 licensePlate 中的数字和空格。

不区分大小写。

如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。

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

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

解题代码

func shortestCompletingWord(licensePlate string, words []string) string {
  //存放licensePlate中的字符
  chars := [26]int32{}
  charnums := 0
  for _, cs := range licensePlate {
    if cs <= 122 && cs >= 97 {
      if chars[cs - 'a'] == 0 {
        charnums ++
      }
      chars[cs - 'a'] ++
    } else if cs <= 90 && cs >= 65 {
      if chars[cs - 'A'] == 0 {
        charnums ++
      }
      chars[cs - 'A'] ++
    }
  }
  index := 0
  length := 0
  for i, word := range words {
    a := charnums
    b := chars
    for _, i2 := range word {
      b[i2 - 'a'] --
      if b[i2 - 'a'] == 0 {
        a --
      }
    }
    if a == 0 {
      if length == 0 {
        length = len(word)
        index = i
      }
      if length > len(word) {
        index = i
        length = len(word)
      }
    }
  }
  return words[index]
}