leet code : Longest_Common_Prefix

こんにちは。かずとよです。

本日も、leetcode解いていきます！

早速、問題文の原文が以下。

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• 0 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

ここから、解読！

【文字列の配列の中から、最も長い共通のプレフィックスを見つけろ。

共通のプレフィックスがない場合は、空の文字列””を返しましょう。】

今回の問題は、割と翻訳したまんまでした。

でも、プレフィックスというのがよく分からん・・・

とりあえず、例文を見た感じ、共通の文字列を探し出すコードを書けばいいのかな？と。早速やってみました。

↑（これが、後の地獄の始まり）

かなりの試行錯誤の末・・・これで、どうだ！！（ここまでに5回以上の誤回答→熟考→修正を繰り返し、心折れかけ。）

def longest_common_prefix(strs)
  str_1 = strs[0]
           # 渡された配列の1つ目
  str_2 = strs[1]
           # 渡された配列の2つ目
  str_include = []
           # 同じ文字が何文字含まれるかを入れるための配列作っとく
  if str_2.include?(str_1.slice(0))
           # 配列の2つ目に配列の1つ目の1文字目が含まれていれば（例文:2のようなものをはじく）
    strs.each do |s|
           # 渡されてる配列を一つずつ繰り返し
      str_count = 0
      str_include_s = 0
      while s.to_s.include?(str_1.slice(0..str_count))
           # 要素に配列の1つ目の文字（頭〜繰り返し回数）が含まれているなら
        str_include_s += 1
        str_count += 1
        if str_count == s.length
           # 文字数文繰り返したら
          break
           # 強制的にループ終了
        end
      end
      str_include << str_include_s
    end
    return str_1.slice(0..str_include.min - 1)
  else
    return ""
  end
end

そして・・・

Runtime Error Message:

Line 7: undefined method `slice' for nil:NilClass (NoMethodError) in solution.rb (longest_common_prefix) Line 29 in solution.rb (__driver_helper__) Line 42 in solution.rb (block in _driver) Line 39 in solution.rb (each) Line 39 in solution.rb (each_slice) Line 39 in solution.rb (_driver) Line 54 in solution.rb (<main>)

Last executed input:

おっそろしくエラーでた。

7行目のsliceメソッドがおかしいよ？

なぜ？VSCodeでは問題なく出力できてるのに？

よく分からんけど、とりあえず、それ以外でできる方法考えるか・・・

ってことで、slice使わず、別の方法を試したりとか、めちゃくちゃ色々試しました。（10誤回答ぐらい。）

でも、一生クリアできない。なぜ？

・・・！！！！

Last executed input:　←これ、ちゃんと見てませんでした。激しく後悔。

inputがだったとき、このエラーでたよって言われてたんですね・・・

そりゃ、からっぽの配列の中身を操作できるわけないですよね。

でも、配列が空でも、その配列の中身を添字つけて指定して、変数定義（上のコードで2行目、3行目）は、エラーにならないんやなーと思いました。

まぁ、気持ちを切り替えて！そうと分かれば！

def longest_common_prefix(strs)
  if strs == []
           # 渡された配列が空なら
      return ""
           # 空の文字列を返す
  else
    str_1 = strs[0]
           # 渡された配列の1つ目
    str_include = []
           # 同じ文字が何文字含まれるかを入れるための配列作っとく
    strs.each do |s|
           # 渡されてる配列を一つずつ繰り返し
      str_count = 0
      str_include_s = 0
      while s.to_s.include?(str_1.slice(0..str_count))
           # 要素に配列の1つ目の文字（頭〜繰り返し回数）が含まれているなら
        str_include_s += 1
        str_count += 1
        if str_count == s.length
           # 文字数文繰り返したら
          break
           # 強制的にループ終了
        end
      end
      str_include << str_include_s
    end
    include_words = str_1.slice(0..str_include.min - 1)
           # 全ての要素に含まれる文字を変数定義
    if include_words == str_1
           # 全ての要素に含まれる文字が配列の1つ目と同じなら
      return ""
           # 空の文字列を返す（このコードを入れるまで、配列の要素が全て同じパターンはなかったので）
    else
      return include_words
    end
  end
end

どや！

Status: 

Time Limit Exceeded

Last executed input:

[""]

制限時間を超えました、だと？

あぁ、配列空っぽは空の文字列で返すようにしたけど、配列に空の文字列がある場合は指定してなかったな・・・

だから、whileで脱出できず、処理し続けちゃって、ちゃんとできてないんだな。

ここから、めちゃくちゃ試行錯誤。

そして、例文で把握しきれていなかったパターンが様々出てきて、その都度コードを修正しながら正解に近づく・・・

Input:["c","acc","ccc"]

Output:"c"

Expected:""

 

ある時出てきた、誤回答の為のこの内容。

cが全ての要素に含まれてるから合ってるやん！って、なりました。

これが、問題文のプレフィックスをちゃんと把握せずに進めた代償です。

僕は、全ての要素に共通して入っている文字だと思って、条件分岐にinclude?を使ってました。

でも、プレフィックスを調べたところ、【頭につく文字列】みたいな事らしく・・・。

発狂。

ここで、1から考え直しです。

大体の型は使いまわせるはずなので、熟考。

include?ではなく、indexを使うことにしました。

そしてまた、トライアンドエラーをひたすら繰り返し・・・

def longest_common_prefix(strs)
  strs_words = strs.join 
           # 渡された配列をひと繋ぎの文字列にする
  if strs.include?("") || strs_words.length == 0
           # 配列に空の文字列が含まれるか、ひと繋ぎにした文字数が0なら
      return ""
           # 空の文字列を返す
  else
    str_1 = strs[0]
           # 渡された配列の1つ目
    str_include = []
           # 同じ文字が何文字含まれるかを入れるための配列作っとく
    strs.each do |s|
           # 渡されてる配列を一つずつ繰り返し
      str_count = 0
      str_include_s = 0
      while s.index(str_1.slice(0..str_count)) == 0
           # 配列の1つ目の文字（頭〜繰り返し回数）が要素の頭にあるなら
        str_include_s += 1
        str_count += 1
        if str_count == s.length
           # 文字数文繰り返したら
          break
           # 強制的にループ終了
        end
      end
      str_include << str_include_s
    end
    include_words = str_1.slice(0..str_include.min - 1)
           # 全ての要素に含まれる文字を変数定義
    if strs.length == 1
           # 配列の中の要素が1つなら
      return include_words
           # 変数include_wordsを返す
    else
           # 配列の中の要素が複数なら
      if strs.all?{|w| w.index(include_words) == 0}
           # 配列の全ての要素の頭に変数include_wordsがあるなら
        return include_words
           # 変数include_wordsを返す
      else
        return ""
      end
    end
  end
end

これで、クリアできました。

ここまでで、35回の誤回答を叩き出しました・・・僕はアホかもしれません。

絶対もっといいコードあると思いますが、さすがに力尽きました。

＊今回の学び:

• 問題文はしっかり読み、分からないところは事前に調べる
• プレフィックスとは、頭につく文字列のこと
• all?メソッドは、配列の要素を繰り返し実行し、その後に書く{}の条件が全て真の場合にtrueを返すメソッド
• indexメソッドは、文字列の中のどこに、指定の文字列が含まれているか返す
• while文などの無限ループになる可能性があるものの中で、if文などでbleakとすることで、ループを脱出できる。
• joinメソッドは、配列をひと繋ぎの文字列にできる。
  オプションがあり、それを使うと区切れたりする？