如何基于最长结尾子串对相似字符串进行分组？

核心规则（从示例反推） #

我们需要构建一个基于域名后缀层级的分组字典：

• 每个分组键是一个域名，满足以下任一条件：
  1. 存在其他域名直接以它为后缀（即去掉该域名最前面的一段就是当前键），且这些域名没有自己的子域名；
  2. 没有任何域名以它为后缀，且没有更短的后缀域名存在于集合中（排除单独的.com）；
• 分组键对应的列表，是所有直接以它为后缀且没有子域名的域名。

简单来说：每个有“子域名”的域名成为分组键，列表是它的最底层子域名；没有子域名也没有父域名的域名也成为分组键，对应空列表。

具体实现步骤 #

1. 构建域名的后缀映射

• 把所有域名按.分割成片段，比如samsung.phone.com分割为["samsung", "phone", "com"]；
• 为每个域名生成父域名（去掉最前面一段后的域名），比如samsung.phone.com的父域名是phone.com，phone.com的父域名是com（直接排除）；
• 建立两个基础映射：
  • child_map：键是父域名，值是该父域名的所有直接子域名；
  • has_child：键是域名，值是布尔值，表示该域名是否存在子域名。

2. 生成最终分组字典

• 初始化空字典；
• 遍历所有域名：
  • 如果该域名没有子域名（has_child[domain]为False）：
    • 找到它的有效父域名（非com且存在于集合中）；
    • 若父域名存在，将该域名添加到父域名对应的列表中；
  • 若该域名有子域名，或者无有效父域名，就将其作为键加入字典（未存在则初始化空列表）；
• 最后校验：确保所有有子域名的域名、无父无子女的域名都在字典中，列表内容正确。

3. 动态更新（支持新增域名）

当添加新域名new_domain时：

• 分割new_domain得到父域名parent_domain（非com则保留）；
• 若parent_domain在集合中：
  • 将new_domain加入child_map[parent_domain]，标记has_child[parent_domain] = True；
  • 若parent_domain之前在某个父域名的列表中，需将它从原列表移除，并将parent_domain作为新键加入字典；
• 将new_domain加入集合，标记has_child[new_domain] = False；
• 重新整理字典的键和列表内容，确保层级关系正确。

示例验证（第三个示例） #

添加hello.samsung.phone.com后：

• 它的父域名是samsung.phone.com（存在于集合中）；
• 将hello.samsung.phone.com加入child_map["samsung.phone.com"]，标记has_child["samsung.phone.com"] = True；
• 把samsung.phone.com从phone.com的列表中移除，同时将samsung.phone.com作为新键加入字典，列表添加hello.samsung.phone.com；
• phone.com的列表仅剩lg.phone.com；
  最终结果和示例完全匹配。

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