NC55：最长公共前缀/LeetCode：14.最长公共前缀
最长公共前缀
https://www.nowcoder.com/practice/28eb3175488f4434a4a6207f6f484f47?tpId=188&&tqId=38627&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
LeetCode 14.最长公共前缀：https://leetcode-cn.com/problems/longest-common-prefix/
解法一：横向扫描
编写一个截取两个字符串公共前缀的方法，通过遍历字符串数组，将数组元素和当前的公共前缀进行传入，以此不断更新当前的最长公共前缀
实现代码1
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
if(strs.length == 0){
return "";
}
String str = strs[0];
for(int i = 1; i<strs.length; i++){ //遍历截取
str = interceptStr(strs[i], str); //更新最长公共前缀
}
return str;
}
public String interceptStr(String str1, String str2){ //截取公共前缀
if("".equals(str1) || "".equals(str2)){
return "";
}
int index = 0;
int len = str1.length() < str2.length() ? str1.length() : str2.length();
for(int i = 0; i<len; i++){
if(str1.charAt(i) != str2.charAt(i)){
index = i-1;
break;
}
index = i;
}
return str1.substring(0, index+1);
}
} 实现代码2
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0 || strs == null){
return "";
}
String reStr = strs[0];
for(int i = 0; i < strs.length; i++){
//将当前得到的公共前缀继续与后面元素进行比较
reStr = getLongestPre(reStr, strs[i]);
}
return reStr;
}
public String getLongestPre(String str1, String str2){
StringBuilder sb = new StringBuilder();
//取长度最小的作为遍历的长度
int len = str1.length() > str2.length() ? str2.length() : str1.length();
for(int i = 0; i < len; i++){
if(str1.charAt(i) == str2.charAt(i)){
sb.append(str1.charAt(i)); //拼接公共前缀
}else{
return sb.toString();
}
}
return sb.toString();
}
}
解法二：纵向扫描
按列进行扫描，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，直到同列字符有不相等或当前列数等于某行字符串长度，即该字符串已遍历完时就直接返回当前的公共前缀
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
if(strs.length == 0 || strs == null){
return "";
}
int len = strs[0].length(); //将第一个字符串的长度作为比较的列数
for(int i = 0; i<len; i++){
char ch = strs[0].charAt(i); //先确定第一个字符串的字符
for(int j = 1; j<strs.length; j++){ //同列字符进行比较
if(i == strs[j].length() || ch != strs[j].charAt(i)){
//同列字符有不相等或当前列数等于某行字符串长度，即该字符串已遍历完
return strs[0].substring(0, i);//直接返回当前公共前缀
}
}
}
return strs[0];
}
} 
投递美团等公司10个岗位 >
