leetcode在力扣 App 中打开
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
premium lock icon相关企业
提示

给你一个下标从 开始的字符串数组 words 。每个字符串都只包含 小写英文字母 。words 中任意一个子串中,每个字母都至多只出现一次。

如果通过以下操作之一,我们可以从 s1 的字母集合得到 s2 的字母集合,那么我们称这两个字符串为 关联的 :

  • 往 s1 的字母集合中添加一个字母。
  • 从 s1 的字母集合中删去一个字母。
  • s1 中的一个字母替换成另外任意一个字母(也可以替换为这个字母本身)。

数组 words 可以分为一个或者多个无交集的  。如果一个字符串与另一个字符串关联,那么它们应当属于同一个组。

注意,你需要确保分好组后,一个组内的任一字符串与其他组的字符串都不关联。可以证明在这个条件下,分组方案是唯一的。

请你返回一个长度为 2 的数组 ans :

  • ans[0] 是 words 分组后的 总组数 。
  • ans[1] 是字符串数目最多的组所包含的字符串数目。

 

示例 1:

输入:words = ["a","b","ab","cde"]
输出:[2,3]
解释:
- words[0] 可以得到 words[1] (将 'a' 替换为 'b')和 words[2] (添加 'b')。所以 words[0] 与 words[1] 和 words[2] 关联。
- words[1] 可以得到 words[0] (将 'b' 替换为 'a')和 words[2] (添加 'a')。所以 words[1] 与 words[0] 和 words[2] 关联。
- words[2] 可以得到 words[0] (删去 'b')和 words[1] (删去 'a')。所以 words[2] 与 words[0] 和 words[1] 关联。
- words[3] 与 words 中其他字符串都不关联。
所以,words 可以分成 2 个组 ["a","b","ab"] 和 ["cde"] 。最大的组大小为 3 。

示例 2:

输入:words = ["a","ab","abc"]
输出:[1,3]
解释:
- words[0] 与 words[1] 关联。
- words[1] 与 words[0] 和 words[2] 关联。
- words[2] 与 words[1] 关联。
由于所有字符串与其他字符串都关联,所以它们全部在同一个组内。
所以最大的组大小为 3 。

 

提示:

  • 1 <= words.length <= 2 * 104
  • 1 <= words[i].length <= 26
  • words[i] 只包含小写英文字母。
  • words[i] 中每个字母最多只出现一次。
通过次数
4,312/13.4K
通过率
32.3%


icon
相关企业

提示 1
Can we build a graph from words, where there exists an edge between nodes i and j if words[i] and words[j] are connected?

提示 2
The problem now boils down to finding the total number of components and the size of the largest component in the graph.

提示 3
How can we use bit masking to reduce the search space while adding edges to node i?


评论 (0)
💡 讨论区规则

1. 请不要在评论区发表题解!

2. 评论区可以发表关于对翻译的建议、对题目的疑问及其延伸讨论。

3. 如果你需要整理题解思路,获得反馈从而进阶提升,可以去题解区进行。

暂无评论

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
words =
["a","b","ab","cde"]
Source