アルゴリズム問題(22/08/05)

問題リンク

https://leetcode.com/problems/longest-common-prefix/

自分の書いたコード

"I couldn't fix this"

解答例(Discussから引用)

ここをクリックすると答えが見れます

一覧のリンク
https://leetcode.com/problems/longest-common-prefix/discuss/?currentPage=1&orderBy=most_votes&query=&tag=ruby

1. これが一番好き

https://leetcode.com/problems/longest-common-prefix/discuss/242255/Ruby-100-Faster-Than-All-Ruby-Submissions

# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
    return "" if strs == []
    common_pre = ""
    short_str = (strs.sort!).delete_at(0)
    short_str.each_char do |c|
         strs.each do |str|
            if(str.start_with?(common_pre + c))
                next 
            else
                return common_pre
            end
         end
        common_pre += c
    end
end

2. コメントで解説がある。

https://leetcode.com/problems/longest-common-prefix/discuss/1741239/Ruby-Solution-(44ms)

# @param {String[]} strs
# @return {String}
def longest_common_prefix(strs)
  # Gets the shortest word.
  # The shortest word of the array can be the longest prefix in best case.
  longest_prefix = strs.min_by { |x| x.length }
  i = 0
  
  # Iterate through the array and check whether the current word starts with longest_prefix.
  # If it doesn't, reduce the length of longest_prefix by 1.
  while (i < strs.length)
    unless strs[i].start_with? longest_prefix
      longest_prefix = longest_prefix[0...-1]
    else
      i += 1
    end
  end

  longest_prefix
end

3. 一番行数が少ない

https://leetcode.com/problems/longest-common-prefix/discuss/1513970/Longest-common-prefix-simple-solution-ruby

def longest_common_prefix(strs)
    strs[0].split('').each_with_index do |char, index|
        strs[1...strs.length].each do |str|
            return str[0...index] if str[index] != char
        end
    end
    strs.first
end

この問題から学んだこと

設問の意味を正しく理解すること

Longest Common Prefix　の意味を勘違いしていた。

o 文字の先頭から共通する文字
x 文字のいずれかの位置から共通する文字

これからもこのような間違いが起きるのは避けられないので、前違えた場合は意図していることをちゃんと理解しないと大変なことになる。

String#rangeは2つの意味がある場合がある(?)

String#[] (Ruby 3.1 リファレンスマニュアル)

上記が参考になりました。
String[a...b]のaとbの間の点の数で、意味合いが違う。
点2つ: rangeオブジェクトが終端を含む場合。インデックスと文字列を対応させる
点3つ: rangeオブジェクトが終端を含まない場合。文字列と「隙間」を対応させる

以上