DAY 3
5
Software Development

## [Day 3] 從LeetCode學演算法 - 0014. Longest Common Prefix (Easy)

``````Question:
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.
``````

Java:

``````class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String pre = strs[0];
int i = 1;
while (i < strs.length){
while (strs[i].indexOf(pre) != 0)
pre = pre.substring(0, pre.length() - 1);
i++;
}
return pre;
}
}
``````

Python支援的min()和max()可以讓我們在List[str]中列出依字母排列順序

(因為排序最大和排序最小在某個index字元相同時，

Python:

``````class Solution:
def longestCommonPrefix(self, strs: 'List[str]') -> 'str':
if not strs: return ""
s1 = min(strs)
s2 = max(strs)

for i, c in enumerate(s1):
if c != s2[i]:
return s1[:i]
return s1
``````

「如果不能用indexOf的話你會怎麼做？」
(可使用String.toCharArray()轉成陣列後再操作)
「如果這組陣列被預期長短差異很大呢？」
(先掃過一遍陣列，拿最短的當pre)
「Best Case和Worst Case的時間複雜度？什麼狀況下會發生？」
(依照你的解法應該有所不同)
「如果加入<0的判斷式的話可以提升這個程式的效率嗎？」
(不一定，因為不保證多快能遇到前綴完全不同的字串，

0015. 3Sum (Medium)