ruby - 在字符串数组中查找字符串数组

问题描述

我已经阅读了很多在字符串中查找子字符串的方法。但就我而言，我需要在字符串中找到一串单词（即子字符串）。我们可以在O(n^3)时间复杂度非常糟糕的情况下实现这一点

例如

sentences = ["jim likes mary", "kate likes tom", "tom does not like jim"]<br/>
phrases = ["jim tom", "likes"]

无论位置如何，我都想在句子中找到完整的短语

在上述情况下，输出将是

[2, [0,1]]

解释：无论句子中所有词组匹配的单词在哪里都返回该句子的索引

1）第一个短语jim tom仅出现在句子的第二个索引中，即tom 不喜欢 jim，因此返回第二个索引
2）而第二个短语likes出现在第一个和第二个数组中，因此返回 0 和 1 索引

我用蛮力做到了，但这不是一种有效的方法

final_arr = []
phrases.each do |phrase|
  temp_arr = []
  sentences.each_with_index do |sentence, index|    
    multiple_word_phrase  = phrase.split(" ")
    if multiple_word_phrase.length > 1
      flag = 1
      multiple_word_phrase.each do |word|
        if !sentence.include?(word)
          flag = 0
          break
        end
      end
      temp_arr << index if flag == 1
    else
      temp_arr << index if sentence.include?(phrase)
    end
  end
  final_arr << temp_arr if temp_arr.any?
end

有什么有效的方法来解决这个问题O(NlogN) Time。我认为这可以通过动态编程来实现，但不知道该怎么做

标签： rubystringalgorithmsubstring

我对 Ruby 不是很熟悉，但是如果你有 hashmaps 和 hashsets 之类的概念，你可以优化它。正如我在评论中提到的，如果您确信算法的时间复杂度是，O(N^3)那么您可以将其优化为O(N^2).

为此，请获取数组sentences并将其转换为哈希图，该哈希图将每个单词与它出现的一组索引相关联。对于您的示例，它看起来像： "jim" -> Set(0, 2), "tom" -> Set(1, 2), "kate" -> Set(1)等等...这将花费时间复杂度O(N)（因为O(1)在哈希图中查找和在 Set 中添加的时间复杂度）

现在，对于每个短语，您将其拆分并取其单词集合的交集。例如，第一个短语的结果将是和Indexes_of("jim")的indexes_of("tom")交集Set(1)。十字路口将带您O(N)进入每个短语。鉴于您有N短语，时间复杂度为O(N^2).

ruby - 在字符串数组中查找字符串数组

问题描述

解决方案

推荐阅读