题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例1:
1 2
| 输入: ["flower","flow","flight"] 输出: "fl"
|
示例2:
1 2 3
| 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
|
说明:
思路1
暴力法,时间复杂度O(n^3)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public String longestCommonPrefix(String[] strs) { String ans = ""; if(strs.length==0) return ans; lable:{ for(int j=0; j<strs[0].length(); j++){ char c = strs[0].charAt(j); for(int i=1; i<strs.length; i++){ if(j>=strs[i].length() || !isCharEqual(c, strs[i], j)){ break lable; } } ans += c; } } return ans; } private boolean isCharEqual(char c, String s, int i){ return c==s.charAt(i); } }
|
思路2
巧用String提供的一些API,例如substring(),判定子串的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public String longestCommonPrefix(String[] strs) { String ans; if(strs.length==0) return ""; ans = strs[0]; for(int i=1; i<strs.length; i++){ while(strs[i].indexOf(ans)!=0){ ans = ans.substring(0, ans.length()-1); if(ans.isEmpty()) return ans; } } return ans; } }
|