如何用Scala从给定字母与字典中找出所有可行拼字游戏单词？

咱们先理清楚问题本质：要找出字典里那些能用给定字母集合拼出来的单词，核心就在于字母出现次数的匹配——单词里每个字母的数量都不能超过可用字母里的对应数量。基于这个思路，我们可以用「频率统计+提前剪枝」的方式实现高效的解决方案。

核心思路拆解 #

1. 预处理可用字母：把可用字母转换成「字母-出现次数」的映射表，这样后续检查单词时不用重复统计可用字母的频率。
2. 快速剪枝：先过滤掉长度超过可用字母总数的单词——毕竟字母总数都不够，肯定拼不出来，这一步能大幅减少后续计算量。
3. 频率对比：对剩下的单词统计字母频率，逐一检查每个字母的出现次数是否都不超过可用字母的对应次数，符合条件的单词就是我们要的结果。

单次查询的最优实现 #

如果只是单次查询字典，直接用下面的代码就足够高效：

def findValidWords(dictionary: List[String], availableLetters: String): List[String] = {
  // 预处理可用字母的频率映射，用view避免创建中间集合提升效率
  val availableCharCounts = availableLetters.groupBy(identity).view.mapValues(_.length).toMap
  val maxAllowedLength = availableLetters.length

  dictionary.filter { word =>
    // 第一步：快速排除长度超标的单词
    if (word.length > maxAllowedLength) false
    else {
      // 统计当前单词的字母频率
      val wordCharCounts = word.groupBy(identity).view.mapValues(_.length)
      // 检查单词的所有字母频率都不超过可用字母的限制
      wordCharCounts.forall { case (char, count) =>
        availableCharCounts.getOrElse(char, 0) >= count
      }
    }
  }
}

// 测试示例
val testDictionary = List("lobby", "bar", "bold", "bobby")
val testLetters = "borblyd"
println(findValidWords(testDictionary, testLetters)) // 输出: List(lobby, bold)

多次查询的优化版本 #

如果需要用同一个字典进行多次不同字母集合的查询，建议提前预处理字典里的单词，把每个单词和它的频率映射缓存起来，这样后续查询会更高效：

// 用case class封装单词和对应的频率映射
case class WordFrequency(word: String, charCounts: Map[Char, Int])

// 预处理字典，生成带频率映射的单词列表
def preprocessDictionary(dictionary: List[String]): List[WordFrequency] = {
  dictionary.map { word =>
    val counts = word.groupBy(identity).view.mapValues(_.length).toMap
    WordFrequency(word, counts)
  }
}

// 基于预处理后的字典进行查询
def findValidWordsPreprocessed(preprocessedDict: List[WordFrequency], availableLetters: String): List[String] = {
  val availableCharCounts = availableLetters.groupBy(identity).view.mapValues(_.length).toMap
  val maxAllowedLength = availableLetters.length

  preprocessedDict.collect {
    case wf if wf.word.length <= maxAllowedLength && 
               wf.charCounts.forall { case (char, count) => availableCharCounts.getOrElse(char, 0) >= count } =>
      wf.word
  }
}

// 使用示例
val preprocessedDict = preprocessDictionary(testDictionary)
println(findValidWordsPreprocessed(preprocessedDict, testLetters)) // 输出: List(lobby, bold)

为什么这是最优解？ #

• 时间效率：预处理可用字母是O(L)（L为可用字母长度），每个单词的处理是O(W)（W为单词长度），总时间复杂度为O(L + N*W)（N为字典单词数），这是这类问题的最优时间复杂度——毕竟每个字母至少需要遍历一次才能统计频率。
• 空间效率：频率映射的空间开销是O(K)（K为不同字母的数量），内存占用非常小。
• 剪枝优化：提前过滤长单词的操作，能在不增加额外开销的前提下，排除大量不可能的候选，进一步提升实际运行效率。

内容的提问来源于stack exchange，提问作者dmigo