Ruby/Rails字典应用：查找由两个短词拼接的6字母单词实现方案

需求背景 #

我们需要实现一个词典处理功能，从dictionary.txt文件中找出所有由两个更短的现有单词拼接而成的6字母单词，参考示例如下：

con + vex => convex
tail + or => tailor
we + aver => weaver

现有基础逻辑 #

目前已经实现了对6字母单词的过滤：

def cleanup_file
  file_data = File.read('dictionary.txt').split
  file_data.reject! { |word| word.size < 6 }
end

核心判断逻辑实现 #

要判断6字母单词是否由两个现有短词拼接，可参考如下方案：

实现思路 #

• 首先需要保留全量单词的查询能力，不能只保留6字母单词，需要用到短单词做匹配校验
• 用Set结构存储全量单词，将存在性判断的时间复杂度降到O(1)，大幅提升查询效率
• 对每个6字母单词遍历所有可能的拆分位置（共5种拆分可能），校验前后两个片段是否都存在于全量单词集合中

完整可运行代码 #

require 'set'

# 加载全量单词到Set，统一转小写避免大小写匹配问题
all_words = Set.new(File.read('dictionary.txt').split.map(&:downcase))
# 筛选所有6字母的单词作为待校验列表
candidate_words = all_words.select { |word| word.length == 6 }

# 存储符合要求的结果
matched_words = []

candidate_words.each do |word|
  # 遍历所有拆分位置：1~5位后拆分
  (1..5).each do |split_index|
    prefix = word[0...split_index]
    suffix = word[split_index..]
    # 校验前后两段都在词典中
    if all_words.include?(prefix) && all_words.include?(suffix)
      matched_words << "#{prefix} + #{suffix} => #{word}"
      # 找到一个有效拆分就跳出，无需遍历剩余拆分位置，不需要去重则可删除该行
      break
    end
  end
end

# 输出所有匹配结果
matched_words.each { |item| puts item }

注意事项 #

• 代码开头需要引入标准库set，如果你的运行环境已经默认加载可以省略
• 如果词典本身已经统一大小写，可去掉map(&:downcase)逻辑
• 如果需要保留同一个单词的所有可能拆分方式，删除break语句即可

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