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
侮辱智商的題目媒吗。不爆粗口了。
**
總結(jié)：簡書，你上傳照片這一個功能怎么老是這么卡倒慧。優(yōu)化下行嗎？
**
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里面走下去汰寓，每走一步，當前結(jié)點必須只有一個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
