LeetCode 917: Reverse Only Letters (Ruby)

Description: https://leetcode.com/problems/reverse-only-letters/

Solution

def reverse_only_letters(string) # O(n)
    result = Array.new(string.length)
    letters = []

    string.each_char.with_index do |char, index|
        if is_letter?(char)
          letters << char
        else
          result[index] = char
        end
    end

    result.each_with_index do |char, index|
      result[index] = letters.pop if char == nil
    end
    result.join
end

def is_letter?(char)
    (/[a-zA-Z]/ =~ char) == 0
end

Benchmark

Runtime: 52 ms, faster than 92.31% of Ruby online submissions for Reverse Only Letters.

Memory Usage: 210.1 MB, less than 30.77% of Ruby online submissions for Reverse Only Letters.

Explanation

1- Create an array with the same amount of elements as the string we are given, and an array (stack) for the letters.

2- Iterate over each char of the string

2.1- If the char is a letter, add it to the letter stack.

2.2- If the char is not a letter, add it to the result array at the same position it was on the original string.

3- Now that our resulting array is filled with non-letters, we iterate through it; If the index we are in is nil, we pop a letter from the letters array and add it to the result array, at the current index position.

4- Join the array, so it becomes a string and return it.