Ruby solution with recurision


  • 0
    T

    Nothing too complicated here, just recursing through. Closing bracket seeking is not particularly smart, could end up being O(n**2) worst case which seems pretty awful.

    I started with a stack approach but found the implementation had a lot of edge cases, recursion seemed more straightforward to implement.

    def decode_string(s)
      return s if s.length < 4
      i = 0
      str = ""
      loop do
        break if i >= s.length
        if is_i?(s[i])
          num, i = get_num(s, i)
          j = find_end(s, i)
          str += decode_string(s[i..j])*num
          i = j + 1
        else
          str += s[i]
          i += 1
        end
      end
      return str.gsub("]", "")
    end
    
    def get_num(s, i)
      num = ""
      last = i + 1
      (i...s.length).each do |j|
        last = j
        break unless is_i?(s[j])
        num += s[j]
      end
      return num.to_i, last + 1
    end
    
    def find_end(s, i)
      k = 0
      (i...s.length).each do |j|
        return j if s[j] == "]" && k == 0
        k += 1 if s[j] == "["
        k -= 1 if s[j] == "]"
      end
    end
    
    def is_i?(char)
       !!(char =~ /\A[-+]?[0-9]+\z/)
    end
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.