Common Letters in 2 Strings

common_characters.md

Common Characters Interview Questions

Write a function that takes two strings as arguments and returns a string containing only the characters found in both strings. Write 2 versions – one that is O(n) and one that is O(n^2).

O(n^2) Solution

def common_characters_O_of_N2(string1, string2)
  common = {}
  string1.each_char do |c|
    string2.each_char do |c_inner|
      if c == c_inner and !common.has_key? c
        common[c] = true
      end
    end
  end
  
  result = common.keys
end

O(n) Solution

def common_characters_O_of_N(string1, string2)
  common = {}
  string1.each_char do |c|
    unless common.has_key? c
      common[c] = false
    end 
  end

  string2.each_char do |c|
    if common.has_key? c
      common[c] = true
    end
  end

  result = common.select {|key, value| value }.keys
end