Write a function to find the longest common prefix string amongst an array of strings.
我的解法
这题easy题我提交了N次才过，数组下标老是outofrange。后来我还是先用一趟遍历把数组最短字符串的长度求出来，再挨个判断subString了。复杂度O(S) ，S是所有字符串的长度之和。
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
if (strs.length == 1) return strs[0];
int minLen = Integer.MAX_VALUE;
for (String s : strs) {
minLen = Math.min(s.length(), minLen);
}
if (minLen == 0) return "";
int end = 1;
for (; end <= minLen; end++) {
for (String s : strs) {
String temp = strs[0].substring(0, end);
if (!s.substring(0, end).equals(temp))
return strs[0].substring(0, end - 1);
}
}
return strs[0].substring(0, end-1);
}
这个写法类似下面的solutions2。但是不需要先遍历一次找最短长度的。
Solution里的解法:
Approach #1 (Horizontal scanning)
第一种，水平搜索，写得真是巧妙啊，先找出前两个string的最长subprefix（拿strs[0]作为prefix），再依次拿这个prefix跟后面的string比，不断extract。Time是O(S)，因为indexOf也是用了O(n)的时间遍历。
Approach #2 (Vertical scanning)
上一种的缺陷是如果这个strs[]里最后一个元素是""这样非常短的元素，那前面的比较就白做了。那么就if (i == strs[j].length() || strs[j].charAt(i) != c)来依次比对每个str的第i个字符。这个写法让我想到我上面的写法，是不需要先求出最短长度的，就用第一个的长度来iterate，遇到不满足的直接return就行了。
Approach #3 (Divide and conquer)
divide and conque也是把我看呆了。。递归。后悔研一算法没认真学王海艳的算法课，好想回去再学一遍。。做了100多题真的没用过分治。
Approach #4 (Binary search)
二分查找也把我看呆了。
Further Thoughts / Follow up
Follow up 也把我看呆了。给一个string q和一个string数组，求它们的LCP。竟然用到了Trie。确实是可以把数组里的这些string用trie来表示的。
( https://leetcode.com/articles/implement-trie-prefix-tree/)
