CODEWITHSUNDEEP
rubystring
Iggy
Iggy

Reputation: 5251

Check whether a string contains all the characters of another string in Ruby

Let's say I have a string, like string= "aasmflathesorcerersnstonedksaottersapldrrysaahf". If you haven't noticed, you can find the phrase "harry potter and the sorcerers stone" in there (minus the space).

I need to check whether string contains all the elements of the string.

string.include? ("sorcerer") #=> true
string.include? ("harrypotterandtheasorcerersstone") #=> false, even though it contains all the letters to spell harrypotterandthesorcerersstone

Include does not work on shuffled string.

How can I check if a string contains all the elements of another string?

Upvotes: 8

Views: 4694

Answers (4)

tokland
tokland

Reputation: 67900

Sets and array intersection don't account for repeated chars, but a histogram / frequency counter does:

require 'facets'

s1 = "aasmflathesorcerersnstonedksaottersapldrrysaahf"
s2 = "harrypotterandtheasorcerersstone"
freq1 = s1.chars.frequency
freq2 = s2.chars.frequency
freq2.all? { |char2, count2| freq1[char2] >= count2 } 
#=> true

Write your own Array#frequency if you don't want to the facets dependency.

class Array
  def frequency
    Hash.new(0).tap { |counts| each { |v| counts[v] += 1 } }
  end
end

Upvotes: 12

Cary Swoveland
Cary Swoveland

Reputation: 110755

I presume that if the string to be checked is "sorcerer", string must include, for example, three "r"'s. If so you could use the method Array#difference, which I've proposed be added to the Ruby core.

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end 

str = "aasmflathesorcerersnstonedksaottersapldrrysaahf"

target = "sorcerer"
target.chars.difference(str.chars).empty?
  #=> true

target = "harrypotterandtheasorcerersstone"
target.chars.difference(str.chars).empty?
  #=> true

If the characters of target must not only be in str, but must be in the same order, we could write:

target = "sorcerer" 
r = Regexp.new "#{ target.chars.join "\.*" }"
  #=> /s.*o.*r.*c.*e.*r.*e.*r/ 
str =~ r
  #=> 2 (truthy)

(or !!(str =~ r) #=> true)

target = "harrypotterandtheasorcerersstone"
r = Regexp.new "#{ target.chars.join "\.*" }"
  #=>  /h.*a.*r.*r.*y* ... o.*n.*e/
str =~ r
  #=> nil

Upvotes: 5

user229044
user229044

Reputation: 239551

A different albeit not necessarily better solution using sorted character arrays and sub-strings:

Given your two strings...

subject = "aasmflathesorcerersnstonedksaottersapldrrysaahf"
search = "harrypotterandthesorcerersstone"

You can sort your subject string using .chars.sort.join...

subject = subject.chars.sort.join # => "aaaaaaacddeeeeeffhhkllmnnoooprrrrrrssssssstttty"

And then produce a list of substrings to search for:

search = search.chars.group_by(&:itself).values.map(&:join)
# => ["hh", "aa", "rrrrrr", "y", "p", "ooo", "tttt", "eeeee", "nn", "d", "sss", "c"]

You could alternatively produce the same set of substrings using this method

search = search.chars.sort.join.scan(/((.)\2*)/).map(&:first)

And then simply check whether every search sub-string appears within the sorted subject string:

search.all? { |c| subject[c] }

Upvotes: 2

ITWorker
ITWorker

Reputation: 995

  1. Create a 2 dimensional array out of your string letter bank, to associate the count of letters to each letter.

  2. Create a 2 dimensional array out of the harry potter string in the same way.

  3. Loop through both and do comparisons.

I have no experience in Ruby but this is how I would start to tackle it in the language I know most, which is Java.

Upvotes: 1

Related Questions