Write a function to find the longest common prefix string amongst an array of strings.
算法分析: 题意很简单, 求字符串数组里面的公用前缀. 首先想到的公用前缀指针为i, 1, 2比较, 取最小i, 再1, 3 比较缩小i的范围. 再1和4, 1和5. 这种方法就比较简单, 时间复杂度为: O(n).
但是我采用的是另外一种分治, 递归的方式, 1, 2, 3, 4, 5 五个字符串, 1,2比较得一个, 2,3比较得一个, 4,5比较得一个, 将得到的3个再以此类方法比较下去,使得最后只剩下两个, 然后求得最终结果, 时间复杂度为: O(nlog2n)
Java:
public class Solution {
public String longestCommonPrefix(String[] strs) {
int len = strs.length;
int i = 0;
if (len == 0)
return "";
if (len == 1)
return strs[0];
if (len == 2) {
if (strs[0].equals(strs[1]))
return strs[0];
int lena = strs[0].length();
int lenb = strs[1].length();
String rst = "";
for (i = 0; i < lena; i++) {
if (i == lenb || strs[0].charAt(i) != strs[1].charAt(i))
break;
rst += strs[0].charAt(i);
}
return rst;
}
int nlen = len / 2 + len % 2;
String cstrs[] = new String[2];
String nstrs[] = new String[nlen];
for (i = 0; i < nlen; i++) {
if (strs[i] == "")
return "";
if (i * 2 == len - 1) {
nstrs[i] = strs[i * 2];
} else {
cstrs[0] = strs[i * 2];
cstrs[1] = strs[i * 2 + 1];
nstrs[i] = this.longestCommonPrefix(cstrs);
}
if (nstrs[i] == "")
return "";
}
return this.longestCommonPrefix(nstrs);
}
}
C++:
public class Solution {
public String longestCommonPrefix(String[] strs) {
int len = strs.length;
int i = 0;
if (len == 0)
return "";
if (len == 1)
return strs[0];
if (len == 2) {
if (strs[0].equals(strs[1]))
return strs[0];
int lena = strs[0].length();
int lenb = strs[1].length();
String rst = "";
for (i = 0; i < lena; i++) {
if (i == lenb || strs[0].charAt(i) != strs[1].charAt(i))
break;
rst += strs[0].charAt(i);
}
return rst;
}
int nlen = len / 2 + len % 2;
String cstrs[] = new String[2];
String nstrs[] = new String[nlen];
for (i = 0; i < nlen; i++) {
if (strs[i] == "")
return "";
if (i * 2 == len - 1) {
nstrs[i] = strs[i * 2];
} else {
cstrs[0] = strs[i * 2];
cstrs[1] = strs[i * 2 + 1];
nstrs[i] = this.longestCommonPrefix(cstrs);
}
if (nstrs[i] == "")
return "";
}
return this.longestCommonPrefix(nstrs);
}
}
Python:
class Solution:
# @return a string
def longestCommonPrefix(self, strs):
l = len(strs)
i = 0
if (l == 0):
return ""
elif (l == 1):
return strs[0]
elif (l == 2):
if (strs[0] == strs[1]):
return strs[0]
la = len(strs[0])
lb = len(strs[1])
rst = ''
for i in range(la):
if (i == lb or strs[0][i] != strs[1][i]):
break;
rst += strs[0][i]
return rst
else:
nl = l / 2 + l % 2
nstrs = []
for i in range(nl):
cstrs = []
tmp = strs[i * 2]
if (tmp == ''):
return ''
if (i * 2 == l - 1):
nstrs.append(tmp)
else:
cstrs.append(tmp)
tmp = strs[i * 2 + 1]
if (tmp == ''):
return ''
cstrs.append(tmp)
tmp = self.longestCommonPrefix(cstrs)
if (tmp == ''):
return ''
nstrs.append(tmp)
return self.longestCommonPrefix(nstrs)
继续查看有关 日志连载的文章
0个访客评论