Ruby #substrings方法的效率优化与最佳实践咨询

1. 时间复杂度分析 #

你的实现时间复杂度是 O(MNL)，其中：

• M 是字典数组的长度
• N 是输入字符串拆分后的单词数量
• L 是单个单词的平均长度

原因是：你嵌套遍历了字典和单词数组，每次还要对单个单词执行子串包含检查（string_word[dic_word]），这个检查的时间和单词长度成正比。如果字典很大或者输入字符串很长，这个复杂度会明显影响性能。

2. 更高效的实现方案 #

方案一：正则表达式批量匹配 #

利用Ruby正则引擎优化过的匹配逻辑，先把字典转成不区分大小写的正则表达式，一次性扫描输入字符串中所有匹配的子串，再统计次数。这种方式避免了嵌套循环，性能会好很多，尤其是字典较大时。

def substrings(string, dictionary)
  # 生成不区分大小写的正则，转义特殊字符避免正则语法冲突
  regex = Regexp.union(dictionary.map { |word| Regexp.escape(word) }, Regexp::IGNORECASE)
  # 扫描所有匹配项，转成小写后统计次数
  string.downcase.scan(regex).each_with_object(Hash.new(0)) do |match, counts|
    counts[match.downcase] += 1
  end
end

方案二：前缀树（Trie）优化 #

如果字典规模极大，可以构建前缀树来减少重复匹配的开销：

1. 把所有字典词插入前缀树
2. 遍历输入字符串的每个起始位置，逐个字符匹配前缀树，记录所有匹配到的字典词
   这种方式的时间复杂度可以降到 O(SK + ML)，其中S是输入字符串总长度，K是字典词的最大长度，M是字典词数量，L是字典词平均长度，适合超大规模字典的场景。

3. 更简洁的实现 #

利用Ruby的内置方法可以大幅简化代码，同时保持可读性：

def substrings(string, dictionary)
  lower_str = string.downcase
  dictionary.each_with_object(Hash.new(0)) do |word, counts|
    # 扫描字符串中所有该词的出现次数，累加到计数哈希
    counts[word] += lower_str.scan(Regexp.new(Regexp.escape(word), Regexp::IGNORECASE)).size
  end.reject { |_, count| count.zero? }
end

这个版本用Hash.new(0)自动初始化计数为0，省去了判断key是否存在的逻辑；用scan直接获取匹配次数，最后过滤掉计数为0的条目，完全符合需求。

4. 代码可读性与变量命名反馈 #

• 变量命名优化：
  • string_array 改成 words 更直观，一看就知道是拆分后的单词集合
  • dic_word 改成 dict_word 或 candidate_substring，避免缩写导致的歧义
  • result 可以改成 substring_counts，明确表示这是子串的计数哈希
• 代码简化：
  • 初始化哈希用 Hash.new(0)，这样直接 counts[word] += 1 就行，不用重复判断key?
  • string.split" " 应该写成 string.split(" ")，符合Ruby代码规范，可读性更好
  • 统一大小写处理：你的代码只把string_word转成小写，但如果字典里有大写词会匹配失败，建议在开头把输入字符串转成小写，避免重复转换
• 逻辑严谨性：
  • string.split(" ") 会把带标点的单词（比如示例中的partner,）当成一个单词，你的实现能匹配到partner是因为子串检查忽略标点，但如果标点在单词中间可能有问题，更健壮的方式是用scan(/\w+/)提取纯单词，不过当前实现能满足示例需求

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