Longest Common Prefix

这道题目其实非常简单。之所以要标记起来是因为发现自己很不擅长处理类似的边界。

问题

[14] Longest Common Prefix  

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

* algorithms
* Easy (34.02%)
* Total Accepted:    530.8K
* Total Submissions: 1.6M
* Testcase Example:  '["flower","flow","flight"]'

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: ["flower","flow","flight"]
Output: "fl"


Example 2:


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


Note:

All given inputs are in lowercase letters a-z.

思路

首先对字符串数组进行排序，找到最短的字符串，那么我们知道最长前缀子字符串的长度是不可能超过这个最短字符串长度的。
然后我们就开始遍历，对于最短字符串中的每个元素，我们遍历整个字符串数组。

def longest_common_prefix(strs)
  return "" if strs.empty?
  sorted = strs.sort{|a| a.length}
  i = 0
  while i < sorted[0].length
    a  = sorted[0][i]
    j = 0
    while j < strs.length - 1
      j+=1
      return sorted[0][0...i] if sorted[j][i] != a
    end
    i += 1
  end
  return sorted[0]
end

后记

联想到生活中的一些目标，其实关键还是去分析自己缺乏什么解决问题的关键要素。
对症下药而不是盲目叠加自我满足感。