14. Longest Common Prefix
Description
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
Solution: (Java)
class Solution {
public String
longestCommonPrefix(String
[] strs
) {
StringBuilder sb
= new StringBuilder();
if (strs
.length
== 0)
return "";
int min_len
= strs
[0].length();
for (int i
= 0; i
< strs
.length
; i
++) {
if (strs
[i
].length() < min_len
) {
min_len
= strs
[i
].length();
}
}
for (int i
= 0; i
< min_len
; i
++) {
char c
= strs
[0].charAt(i
);
int flag
= 1;
for (int j
= 1; j
< strs
.length
; j
++) {
if (c
!= strs
[j
].charAt(i
)) {
flag
= 0;
break;
}
}
if (flag
== 1)
sb
.append(c
);
else
break;
}
return sb
.toString();
}
}
思路
寻找字符串最长公共前缀，首先遍历一遍字符串数组，找出最小的字符串长度（最长公共前缀的长度不会超过这个），然后以此长度为循环范围，遍历每个字符串，只有每个字符串都包含相同的该字符，才把该字符加入公共前缀中。
更多思路可以参考：LeetCode | Solution
