Как узнать, появляются ли символы одной строки по порядку во второй строке

Question

Учитывая две строки, «word» и «key», как я могу написать метод sequence_search(word, key), который возвращает true (else false), если символы в «key» появляются в том же порядке (но не обязательно смежные) в "слове"?

Предположим, например, key = 'cat'. Метод должен возвращать true, если «слово» равно "arcata", "c1a2t3" или "coat", но возвращать false, если «слово» равно "cta".

Вот моя попытка ответить вопрос:

def sequence_search(word, key)
    arr = []
    i = 0
    while i < word.length
     word[i].include?(key)
    arr >> word[i]
      end
      i+= 1
    end
      if arr.join == key  # line raising exception
        return true
      else false
      end
    end

Когда я запускаю свой код, я получаю исключение:

NameError (undefined local variable or method `arr' for main:Object)

в указанной строке. Зачем? А есть ли способ лучше написать метод?

Answer 1

Чтобы определить проблему с вашим кодом, полезно сначала отформатировать его должным образом.

def sequence_search(word, key)
  arr = []
  i = 0
  while i < word.length
    word[i].include?(key)
    arr >> word[i]
  end
  i += 1
end

if arr.join == key  # line raising exception
  return true
else
  false
end

end

Как видите, метод не заканчивается там, где вы думали, и есть лишний end. Вот некоторые из проблем:

• while l oop никогда не закончится, потому что i не увеличивается в пределах цикла;
• arr >> word[i] должно быть arr << word[i]
• word[i].include?(key) не имеет эффекта, так как возвращаемое значение не используется (вы можете захотеть arr << word[i] if word[i].include?(key));
• logi c неверен: после исправления кода если word = "acat" (который содержит "cat"), вы пытаетесь построить массив arr #=> ["a", "c", "a", "t"], к которому вы присоединитесь (чтобы получить "acat") и сравнить с "cat" (if arr.join == key), что (ошибочно) потерпеть поражение.

Вот два способа написать метод.

Используйте String#index для перехода по word для поиска каждого символа key

def sequence_search(word, key)
  i = -1
  key.each_char.all? { |c| i = word.index(c,i+1) }
 end

sequence_search("arcata", "cat") #=> true
sequence_search("c1a2t3", "cat") #=> true
sequence_search("cta", "cat")    #=> false
sequence_search("coat", "cat")   #=> true

См. String # index , уделяя особое внимание необязательному второму аргументу, смещению в строке, в котором поиск должен начаться.

Используйте регулярное выражение

def sequence_search(word, key)
  word.match?(/#{key.chars.join(".*")}/)
end

sequence_search("arcata", "cat") #=> true
sequence_search("c1a2t3", "cat") #=> true
sequence_search("cta", "cat")    #=> false
sequence_search("coat", "cat")   #=> true

Когда key = "cat" ,

/#{key.chars.join(".*")}/
  #=> /c.*a.*t/

Регулярное выражение гласит: «соответствует 'c', за которым следует ноль или более символов, за которыми следует 'a', за которым следует ноль или более символов, за которыми следует 't'.

Answer 2

Удалите все символы, которых нет в ключе, и проверьте, включен ли ключ в остаток:

def sequence_search(str, key)
  str.delete("^#{key}").include?(key) # ^ means "everything but"
end

Answer 3

Полезная информация:

require 'benchmark'

N = 100_000

puts 'Ruby %s' % RUBY_VERSION

def cary1(word, key)
  i = -1
  key.each_char.all? { |c| i = word.index(c,i+1) }
end

def cary2(word, key)
  word.match?(/#{key.chars.join(".*")}/)
end

def steenslag(str, key)
  str.delete("^#{key}").include?(key) # ^ means "everything but"
end

def estebes(word, key)
  arr = key.split('')
  arr.each do |c|
    return false if word.index(c) == nil
    word.slice!(0, word.index(c) + 1)
    return true if arr.last == c
  end
end

Benchmark.bmbm do |x|
  x.report('cary1')     { N.times { cary1("arcata", "cat") } }
  x.report('cary2')     { N.times { cary2("arcata", "cat") } }
  x.report('steenslag') { N.times { steenslag("arcata", "cat") } }
  x.report('estebes')   { N.times { estebes("arcata", "cat") } }
end

# >> Ruby 2.7.1
# >> Rehearsal ---------------------------------------------
# >> cary1       0.128231   0.000218   0.128449 (  0.128572)
# >> cary2       0.461305   0.000509   0.461814 (  0.462048)
# >> steenslag   0.055794   0.000026   0.055820 (  0.055847)
# >> estebes     0.263030   0.000185   0.263215 (  0.263399)
# >> ------------------------------------ total: 0.909298sec
# >> 
# >>                 user     system      total        real
# >> cary1       0.131944   0.000141   0.132085 (  0.132227)
# >> cary2       0.453452   0.000626   0.454078 (  0.454374)
# >> steenslag   0.055342   0.000026   0.055368 (  0.055394)
# >> estebes     0.255280   0.000156   0.255436 (  0.255607)

Использование Fruity :

require 'fruity'

puts 'Ruby %s' % RUBY_VERSION

def cary1(word, key)
  i = -1
  key.each_char.all? { |c| i = word.index(c,i+1) }
end

def cary2(word, key)
  word.match?(/#{key.chars.join(".*")}/)
end

def steenslag(str, key)
  str.delete("^#{key}").include?(key) # ^ means "everything but"
end

def estebes(word, key)
  arr = key.split('')
  arr.each do |c|
    return false if word.index(c) == nil
    word.slice!(0, word.index(c) + 1)
    return true if arr.last == c
  end
end

compare do
  _cary1     { cary1("arcata", "cat") } 
  _cary2     { cary2("arcata", "cat") } 
  _steenslag { steenslag("arcata", "cat") } 
  _estebes   { estebes("arcata", "cat") } 
end

# >> Ruby 2.7.1
# >> Running each test 8192 times. Test will take about 2 seconds.
# >> _steenslag is faster than _cary1 by 2x ± 0.1
# >> _cary1 is faster than _estebes by 2x ± 0.1
# >> _estebes is faster than _cary2 by 2x ± 0.1

Answer 4

Я не знаю, какое решение вы ищете, но это быстрое решение для меня:

def sequence_search(word, key)
  arr = key.split('')
  arr.each do |c|
    return false if word.index(c) == nil
    word.slice!(0, word.index(c) + 1)
    return true if arr.last == c
  end
end


sequence_search('cat', 'cat') #=> true
sequence_search('cdadsas', 'cat') #=> false
sequence_search('gdfgddfgcgddadsast', 'cat') #=> true
sequence_search('gdfgddfgcgddadsast', 'cat4') #=> false