需求实现：Dart函数输出覆盖全部单词的最少字母

需要编写一个Dart函数，输出能覆盖所有给定单词的最少字母集合。例如输入单词列表["apple", "table", "rum", "bread"]时，函数应输出类似{"a", "r"}（或{"e", "m"}等符合条件的组合）。原因是：

• apple、table、bread这三个单词都包含a或e，选其中一个就能覆盖这三个词
• rum需要从r、u、m中选一个
• 所以最少只需要2个字母就能覆盖所有单词

但当前尝试的代码只会输出"No common letters."，无法满足需求，代码如下：

void findCommonLetters(List<String> words) {
  if (words.isEmpty) {
    print("No common letters.");
    return;
  }

  Set<String> commonLetters = Set.from(words[0].split(''));

  for (int i = 1; i < words.length; i++) {
    final word = words[i];
    final wordLetters = Set.from(word.split(''));

    commonLetters = commonLetters.intersection(wordLetters);
  }

  if (commonLetters.isEmpty) {
    print("No common letters.");
  } else {
    print("Common letters: ${commonLetters.join(", ")}");
  }
}

void main() {
  List<String> words = ["apple", "banana", "sun"];
  findCommonLetters(words);
}

你的现有代码是在找所有单词的公共交集字母，这和需求的「覆盖所有单词的最少字母集合」完全是两个问题。后者属于集合覆盖问题的简化场景，我们可以通过以下思路实现：

实现思路 #

• 先收集所有出现过的字母，生成所有可能的字母子集（从最小长度开始尝试）
• 对每个子集，检查是否能覆盖所有单词（即每个单词至少包含子集中的一个字母）
• 找到第一个满足条件的最小子集，返回即可

Dart 实现代码 #

import 'dart:math';

// 生成所有指定长度的字母子集
List<Set<String>> generateSubsets(Set<String> allLetters, int length) {
  List<String> letters = allLetters.toList();
  List<Set<String>> subsets = [];
  
  // 用二进制位掩码生成组合
  int total = pow(2, letters.length).toInt();
  for (int mask = 0; mask < total; mask++) {
    Set<String> subset = {};
    for (int i = 0; i < letters.length; i++) {
      if ((mask >> i) & 1 == 1) {
        subset.add(letters[i]);
      }
    }
    if (subset.length == length) {
      subsets.add(subset);
    }
  }
  return subsets;
}

// 检查子集是否能覆盖所有单词
bool coversAllWords(Set<String> subset, List<String> words) {
  for (String word in words) {
    bool hasMatch = false;
    for (String letter in subset) {
      if (word.contains(letter)) {
        hasMatch = true;
        break;
      }
    }
    if (!hasMatch) return false;
  }
  return true;
}

// 找到覆盖所有单词的最少字母集合
Set<String>? findMinCoverLetters(List<String> words) {
  if (words.isEmpty) return null;
  
  // 收集所有出现过的字母
  Set<String> allLetters = {};
  for (String word in words) {
    allLetters.addAll(word.split(''));
  }
  
  // 从最小长度开始尝试
  for (int k = 1; k <= allLetters.length; k++) {
    List<Set<String>> subsets = generateSubsets(allLetters, k);
    for (Set<String> subset in subsets) {
      if (coversAllWords(subset, words)) {
        return subset;
      }
    }
  }
  
  return null; // 理论上不会走到这里，因为全字母集合肯定能覆盖
}

void main() {
  List<String> words = ["apple", "table", "rum", "bread"];
  Set<String>? result = findMinCoverLetters(words);
  
  if (result != null) {
    print("最少覆盖字母集合: ${result.join(", ")}");
    // 示例输出可能是 "a, r" 或 "e, m" 等
  } else {
    print("无法找到覆盖集合");
  }
}

说明 #

• 这个实现通过枚举子集的方式找最小覆盖集合，对于单词数量和字母数量不多的场景足够高效
• 如果处理大规模数据，可能需要更优化的算法（比如贪心算法近似解，不过贪心不一定能得到最优解）
• 示例输入运行后会返回第一个找到的最小子集，比如{"a", "r"}或者其他符合条件的组合

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