Ruby如何利用给定字典词库拆分目标字符串 修复现有方法仅返回false问题

原代码错误原因 #

• 未定义变量strArr，运行时会直接抛出变量未找到异常
• 逻辑完全不符合需求：include?方法用于判断单个元素是否存在于数组中，你直接传入拆分后的字典数组做参数，永远只会返回false，完全没有实现字符串拆分匹配的逻辑

实现思路 #

这是典型的「单词拆分」问题，我们需要用动态规划先判断字符串是否可被字典拆分，再用回溯法收集合法的拆分结果，按你的需求返回第一个匹配的拆分结果即可。

正确实现代码 #

def word_split(string_array)
  target = string_array[0]
  word_dict = string_array[1].split(',').to_set # 转成Set提升单词查询效率
  len = target.length
  # dp[i] 表示target前i个字符是否可以被合法拆分
  dp = Array.new(len + 1, false)
  dp[0] = true # 空字符串默认可拆分
  
  # 动态规划判断可拆分性，同时记录合法拆分的前驱位置
  prev = Array.new(len + 1) { [] }
  (1..len).each do |i|
    (0...i).each do |j|
      if dp[j] && word_dict.include?(target[j...i])
        dp[i] = true
        prev[i] << j
      end
    end
  end
  
  return nil unless dp[len] # 不可拆分直接返回空
  
  # 回溯获取拆分路径
  result = []
  backtrack = lambda do |pos, path|
    if pos == 0
      result << path.reverse.join(',')
      return
    end
    prev[pos].each do |p|
      backtrack.call(p, path + [target[p...pos]])
    end
  end
  
  backtrack.call(len, [])
  result.first # 返回第一个匹配的拆分结果，和示例输出一致
end

# 示例测试
string_array = ["baseball", "a,all,b,ball,bas,base,cat,code,d,e,quit,z"]
puts word_split(string_array) # 输出 base,ball

代码说明 #

• 字典转集合后单词查询复杂度从O(n)降到O(1)，整体运行效率更高
• dp数组负责判断字符串能否拆分，prev数组记录所有合法拆分的位置节点，避免回溯时重复校验
• 回溯从字符串末尾倒推到开头，收集所有合法拆分组合，按需返回即可

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