scoldboy
BAN USERRuby, Memoized, I think nlog(n) worst case time....
If anyone can figure out the time complexity would be great.
dict = {}
%w(hello to the world).each do |word|
i = 0
res = 0
while i < word.length
res ^= word[i].ord
i += 1
end
dict[res] = dict[res] ? [word] + dict[res] : [word]
end
def is_word str, dict
i = 0
res = 0
while i < str.length
res ^= str[i].ord
i += 1
end
return nil unless dict[res]
dict[res].each do |word|
return word if word.split('').sort == str.split('').sort
end
nil
end
def unscramble str, dict, hash = {}
return '' if str.length == 0
str.length.times do |idx|
value = is_word(str[0..idx], dict)
next unless value
rest = hash[str[idx+1...str.length]] ? hash[str[idx+1...str.length]] : unscramble(str[idx+1...str.length], dict)
next unless rest
return hash[str] = rest == '' ? value : value + " " + rest
end
return nil
end
I did it with and without dynamic programming in Ruby
def sums coins, quants, pos = 0, count = 0
res = [0]
res += sums(coins, quants, pos, count+1).map{ |el| el += coins[pos]} if count < quants[pos]
res += sums(coins, quants, pos+1, 0) if pos < coins.length - 1
res.uniq.sort.reverse
end
def sums_dp coins, quants, hash = {}, pos = 0, count = 0
res = [0]
if count < quants[pos]
value = hash[[pos, count+1]] || sums(coins, quants, hash, pos, count+1).map{ |el| el += coins[pos]}
res += value
end
if pos < coins.length - 1
value = hash[[pos+1, 0]] || sums(coins, quants, hash, pos+1, 0)
res += value
end
hash[[pos, count]] = res.uniq.sort.reverse
end
class Node
attr_accessor :value, :left, :right
def initialize value
@value = value
@left = nil
@right = nil
end
end
class Tree
attr_accessor :root
def initialize
@root = nil
end
def paths node = @root
return [[node.value]] unless node.right || node.left
res = []
res += [[node.value]]
res += paths(node.left).map{|el| el += [node.value]} if node.left
res += paths(node.right).map{|el| el += [node.value]} if node.right
res
end
end
I used BFS.
def move arr, idx
loc = arr.index(-1)
return false if idx == loc
arr = arr.dup
arr[loc], arr[idx] = arr[idx], arr[loc]
arr
end
def moves arr
res = []
arr.length.times do |idx|
if move(arr, idx)
res << move(arr, idx)
end
end
res
end
def solved_arr arr
i = 1
solved = [-1]
while i < arr.length
solved << i
i += 1
end
solved
end
def bfs arr
hash = {}
hash[arr] = [0, arr]
solved = solved_arr(arr)
break_loop = false
queue = [arr]
until break_loop
past = queue.shift
moves = moves(past)
moves.each do |el|
queue << el unless hash[el]
hash[el] = past unless hash[el]
break_loop = true if el == solved
end
end
res = []
while hash[solved] != arr
res << solved
solved = hash[solved]
end
res << solved
res << arr
res.reverse
end
Ruby
- scoldboy December 30, 2016