Time: O(n), Space: O(1)
写法1:
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
// loop every index in string
for (int i = 0; i < strs[0].length(); i++) {
char cur = strs[0].charAt(i);
// loop every string
for (int j = 0; j < strs.length; j++) {
if (strs[j].length() == i || cur != strs[j].charAt(i)) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
}
另外一种写法:
class Solution {
// Consider edge cases:
// ["a"], ["a", ""], ["a", "b"]
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
if (strs.length == 1) {
return strs[0];
}
String curCommon = strs[0];
for (int i = 1; i < strs.length; i++) {
curCommon = getCommonPrefix(curCommon, strs[i]);
if (curCommon == "") {
return curCommon;
}
}
return curCommon;
}
private String getCommonPrefix (String str1, String str2) {
char[] char1 = str1.toCharArray();
char[] char2 = str2.toCharArray();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < char1.length && i < char2.length; i++) {
if (char1[i] == char2[i]) {
sb.append(char1[i]);
} else {
break;
}
}
return sb.toString();
}
}