leetcode-14最长公共前缀
题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串
""
。示例 1:
输入: ["flower","flow","flight"] 输出: "fl"示例 2:
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。说明:
所有输入只包含小写字母
a-z
。
idea:用第一个字符串的每一个字符去和其他的字符串的对应位置字符去比对,如果都相同 ,那么这个字符属于公共前缀;再判断下一个,直到不相同字符出现/有字符串结束,就结束比较。
算法:
如果数组只有一个元素,那么直接返回第一个字符串即可
如果数组元素多于一个,继续
计算字符串数组中最短字符串的长度(shortest)
遍历第一个元素(form 0 to shortest)->遍历更多没用,我们在找公共的元素
内嵌遍历字符串数组
如果存在对应位置的字符与第一个字符串的字符不同,直接结束,返回结果
如果对应位置字符都相同,那么将此字符连接到结果后面。
返回结果字符串。
1 class Solution { 2 public String longestCommonPrefix(String[] strs) { 3 if(strs.length == 1) 4 { 5 return strs[0]; 6 } 7 8 String ans = ""; 9 if(strs.length > 1) 10 { 11 int i, j; 12 boolean sameFlag; 13 int shortest = strs[0].length(); 14 for(i=0; i<strs.length; i++) 15 { 16 if(strs[i].length() < shortest) 17 { 18 shortest = strs[i].length(); 19 } 20 } 21 for(i=0; i<shortest; i++) 22 { 23 sameFlag = true; 24 char c1 = strs[0].charAt(i); 25 for(j=1; j<strs.length; j++) 26 { 27 char c2 = strs[j].charAt(i); 28 if(c1 != c2) 29 { 30 sameFlag = false; 31 } 32 } 33 34 if(sameFlag == true) 35 { 36 ans += strs[0].charAt(i); 37 } 38 else 39 { 40 break; 41 } 42 } 43 } 44 return ans; 45 } 46 }