Question:
Paste_Image.png
My code:
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null)
return null;
if (strs.length == 0)
return "";
if (strs.length == 1)
return strs[0];
int minLength = Integer.MAX_VALUE;
for (int i = 0; i < strs.length; i++) {
if (minLength > strs[i].length())
minLength = strs[i].length();
}
String result = "";
boolean isOver = false;
for (int i = 0; i < minLength; i++) {
for (int j = 0; j < strs.length - 1; j++) {
if (strs[j].charAt(i) != strs[j + 1].charAt(i)) {
isOver = true;
break;
}
}
if (!isOver)
result += strs[0].charAt(i);
else
break;
}
return result;
}
}
My test result:
Paste_Image.png
侮辱智商的题目。不爆粗口了。
**
总结：简书，你上传照片这一个功能怎么老是这么卡。优化下行吗？
**
Anyway, Good luck, Richardo!
这道题目竟然没做出来，感觉自己的思考能力越来越差了，碰到新题，第一个想到的就是看答案。
this is not right!
My code:
Horizontal scanning
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.length() == 0) {
return "";
}
}
}
return prefix;
}
}
Vertical Scanning
My code:
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
int i = 0;
while (i < strs[0].length()) {
char curr = strs[0].charAt(i);
for (int j = 1; j < strs.length; j++) {
if (i < strs[j].length() && strs[j].charAt(i) == curr) {
continue;
}
else {
return strs[0].substring(0, i);
}
}
i++;
}
return strs[0];
}
}
reference:
https://leetcode.com/articles/longest-common-prefix/
这篇文章分析的很好。
还有两种方法：
一个是 divide and conquer,把strs[] 分成两块去找LCP,然后再merge
一个是 binary search, 先找到最短字符串，s[0, end]
然后看 s[0, mid] 是不是 CP,
如果是， begin = mid,
如果不是， end = mid - 1
以此类推。
然后最后有个follow up,
如果给定一个 strs[], 还有一个输入string p,
找 p 在 strs[] 中的LCP
怎么做？
最快的方法就是建Trie,然后顺着 p 在Trie里面走下去，每走一步，当前结点必须只有一个link，而且必须不是end point
然后找到 LCP
然后还有种方法解决这道题目。
将 strs[] 全部排序，然后比较第一个和最后一个字符串，找 LCP
My code:
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
Arrays.sort(strs);
String s1 = strs[0];
String s2 = strs[strs.length - 1];
int i = 0;
for (; i < s1.length(); i++) {
if (i < s2.length() && s1.charAt(i) == s2.charAt(i)) {
continue;
}
else {
break;
}
}
return s1.substring(0, i);
}
}
Anyway, Good luck, Richardo! -- 09/17/2016
