CODEWITHSUNDEEP
ruby
Matt Mowris
Matt Mowris

Reputation: 21

Substring in string

This function should take in two strings "daBcD" and "ABC". It is trying to create the string "b" from the letters in "a". You can only delete or capitalize letters, you cant change them. b will always contain all uppercase letters.

def abbreviation(a, b)
aArray = a.split('')
idx = 0
aArray.each do |char|
    #print "char: #{char}\n"
    #print "Before loops: #{aArray}\n"
    if char.casecmp(b[idx]) == 0
        char.upcase!
        idx += 1
        #print "char: #{char}\nArry: #{aArray}\n"
        #print "idx: #{idx}\n siz: #{b.size}\n"
        if idx == b.size
            aArray.reject! {|i| i == 'delete'}
            aArray.slice!(b.size)
            break
          end
    else
      aArray[aArray.index(char)] = 'delete'
      #print "deleted, now is: #{aArray}\n"
    end
  end
  res = aArray.join('')
  if res == b
    return 'YES'
  else
    return 'NO'
  end
end

This works for a couple test cases, but fails most of them. Can someone describe a better approach?

Upvotes: 1

Views: 75

Answers (2)

Amadan
Amadan

Reputation: 198314

The absolutely easiest way is via regular expression:

def abbreviation(a, b)
  re = Regexp.new(b.each_char.map(&Regexp.method(:quote)).join('.*'), Regexp::IGNORECASE)
  !!re.match(a)
end

abbreviation("daBcD", "ABC")
# => true
abbreviation("daCbD", "ABC")
# => false

For the input ABC, we'll construct a regular expression /A.*B.*C/i, then test the other string against it. The .* construct will account for "deletion"; the IGNORECASE option for "capitalisation".

EDIT: If the problem is further constrained that only lowercase letters can be deleted, as suggested by the comments,

def abbreviation(a, b)
  # (b is uppercase only)
  re_pat = b.each_char.map { |c| "[#{c}#{c.downcase}]"}.join('[[:lower:]]*')
  re = Regexp.new(re_pat)
  !!re.match(a)
end

p abbreviation("daBcD", "ABC") # => true
p abbreviation("daBdcD", "ABC") # => true
p abbreviation("daBDcD", "ABC") # => false

Upvotes: 0

Cary Swoveland
Cary Swoveland

Reputation: 110665

I have assumed the problem is to determine whether the characters in b appear in a (case indifferent), in the same order as in b, but not necessarily contiguous in a (see the second example below). If they do I return an array of the indices at which they appear in a. If there is no match, nil is returned.

def doit(a, b)
  m = a.match(Regexp.new(b.each_char.map { |c| "(#{c})" }.join('.*'),
                         Regexp::IGNORECASE))
  return nil if m.nil?
  (1..b.size).map { |i| m.begin(i) }
end

doit "daBcD", "ABC"
  #=> [1, 2, 3]
doit "daXBDecf", "ABC"
  #=> [1, 3, 6]
doit "dacBD", "ABC"
  #=> nil

For the first example the regular expression is as follows.

Regexp.new("ABC".each_char.map { |c| "(#{c})" }.join('.*'), Regexp::IGNORECASE)
  #=> /(A).*(B).*(C)/i

Upvotes: 1

Related Questions