Sprawdź, czy ciąg zawiera wszystkie znaki innego ciągu w Ruby

Question

Załóżmy, że mam ciąg znaków, taki jak string= "aasmflathesorcerersnstonedksaottersapldrrysaahf". Jeśli jeszcze tego nie zauważyłeś, możesz znaleźć tam frazę "harry potter and the sorcerers stone" (minus spację).

Muszę sprawdzić, czy string zawiera wszystkie elementy ciągu.

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

Opcja "Uwzględnij" nie działa w przypadku tasowania ciągów.

Jak mogę sprawdzić, czy ciąg znaków zawiera wszystkie elementy innego ciągu?

Answer 1

zestawy i tablica skrzyżowanie nie stanowią powtarzające się znaki, ale histogram/frequency counter robi:

require 'facets' 

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

Napisz Array#frequency jeśli nie chcesz się do aspektów uzależnienia.

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

Answer 2

1. Utwórz 2 wymiarową tablicę ze swojego string literę banku, aby skojarzyć liczbę liter każdego listu.

2. Utwórz dwuwymiarową tablicę z łańcucha harry potter w ten sam sposób.

3. Przeprowadź pętlę przez oba i wykonaj porównania.

Nie mam żadnego doświadczenia w Ruby, ale w ten sposób zacznę rozwiązywać problem w języku, który znam najbardziej, czyli w Javie.

Answer 3

Przypuszczam, że jeśli ciąg do sprawdzenia to „czarodziej”, string musi obejmować, na przykład, trzy „r” 'ów. Jeśli tak, możesz użyć metody Array#difference, którą zaproponowałem dodać do jądra Ruby.

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 

Jeśli bohaterowie cel nie musi być tylko w str, ale musi być w tej samej kolejności, możemy napisać:

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

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

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

Answer 4

różne, choć niekoniecznie lepsze rozwiązania z wykorzystaniem posortowanych tablic znaków i pod-łańcuchów:

wyraziłeś dwa ciągi ...

subject = "aasmflathesorcerersnstonedksaottersapldrrysaahf" 
search = "harrypotterandthesorcerersstone" 

można sortować napisu za pomocą .chars.sort.join ...

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

I wtedy produkować listę podciągów, aby szukać:

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

Można alternatywnie produkować ten sam zestaw podciągów za pomocą this method

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

a następnie po prostu sprawdzić, czy każdego wyszukiwania podtynkowy pojawia się wewnątrz posortowanego ciągu tematycznego:

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