できません.. アルゴリズム的にはできてるんだけど1、答えを得るのに1時間とかorz..
5秒で答えなきゃいけないのに。あとグローバル変数を使ってしまった。
どうも高速化は苦手です。そこに注力する気がなかなか起きない..
レーベンシュタイン距離が1の語同士をfriendとして、与えられた辞書におけるhelloの語から始まるfriendの輪に含まれるすべての語の数を答える。
#!/usr/bin/env ruby require "open-uri" def network_for(word, dic) find_friends(word, dic) end def find_friends(word, dic) words, $dic = dic.partition { |w| lev_dist_one?(word, w) } if words.empty? 0 else words.inject(0) { |sum, w| sum + (1 + find_friends(w, $dic)) } end end def lev_dist_one?(word1, word2) case (word1.size - word2.size) when 0 same_when_one_sub?(word1, word2) when 1 same_when_one_ins_or_rem?(word1, word2) when -1 same_when_one_ins_or_rem?(word2, word1) else false end end def same_when_one_sub?(word1, word2) word1.size.times.any? do |i| w1, w2 = word1.dup, word2.dup w1.slice!(i,1); w2.slice!(i,1) w1 == w2 end end def same_when_one_ins_or_rem?(longer, shorter) longer.size.times.any? do |i| w = longer.dup w.slice!(i,1) w == shorter end end def main(word, dic) dic = dic.map(&:chomp) - [word] network_for(word, dic) end DIC_URL = "https://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt" puts main('causes', open(DIC_URL))
100円〜で好評発売中！M'ELBORNE BOOKS
