我的问题很简单,我有一组子字符串,需要计算这些子字符串在一个特定字符串中出现的次数。以下是我的代码:
string = "..."
substrings = ["hello", "foo", "bar", "brol"]
count = 0
substrings.each do |sub|
count += 1 if string.include?(sub)
end
在这个例子中,我们对整个字符串进行了4次运算,这是相当耗费资源的。你应该如何优化这个过程?
我的问题很简单,我有一组子字符串,需要计算这些子字符串在一个特定字符串中出现的次数。以下是我的代码:
string = "..."
substrings = ["hello", "foo", "bar", "brol"]
count = 0
substrings.each do |sub|
count += 1 if string.include?(sub)
end
这个方法利用Regexp.union
仅运行一次来处理字符串:
string = 'hello there! this is foobar!'
substrings = ["hello", "foo", "bar", "brol"]
string.scan(Regexp.union(substrings)).count
# => 3
n
的字符串和长度为m
的子字符串,原始解决方案的复杂度为O(m*n)
,而此解决方案的复杂度为O(m+n)
。
子字符串
在字符串中至少出现一次,而我的解决方案计算任何一个子字符串
出现了多少次:op_solution('hello hello there', ["hello", "foo", "bar", "brol"])
# => 1
uri_solution('hello hello there', ["hello", "foo", "bar", "brol"])
# => 2
这也解释了为什么我的解决方案对于长字符串也非常慢——虽然它只在输入字符串上进行一次遍历,但必须通过全部的字符,而原始代码在第一次单词出现时就停止了。
我的结论是——采用@Arup的解决方案。它不会比您的更快,只是更简洁,但我想不出更好的方法 :)
write as :-
substrings.count { |sub| string.include?(sub) }
O(m*n)
,而扫描解决方案的复杂度为O(m+n)
。 - Uri Agassisubstrings.count { |sub| string[sub] }
怎么样? - Arup Rakshitm
次),它都遍历整个字符串(长度为 n
),这给出了复杂度为 O(m*n)
。这比您原来的答案更简洁,非常符合 Ruby 的习惯用法,但运行时间(本质上)是相同的。 - Uri Agassisubtrings.collect { |i| string.scan(i).count }.sum
优雅。