LeetCode----Longest Common Prefix

Longest Common Prefix

要求：传入一个字符串数组，从中找到数组中每个字符串元素都有的最长前缀，然后返回，如果没有则返回“”

思路：

第一步：先初始化String result=""；

第二步：先判断strs数组是否等于null或者元素个数等于0,如果是则就返回result=""；判断如果元素个数==1，则return strs[0];

第三步：双重循环比较数组里的的字符串： 第一重循环确定是每个字符串的第i个字符来比较， 第二重循环就取出 第一个字符串和第j个字符串，如果（i<第一个字符串的长度&&i<第j个字符串的长度）就把{ 第一个字符串的第i个字符取出来和后面第j个字符串的第i个字符取出来比较是否相同，如果不相同就跳出最外层循环,如果相同就继续 } Else 跳出最外层循环；

第四步：如果最后(i-1)=-1，说明没有相同前缀，直接return result="",如果(i-1)>-1,就把第一个字符串的第0到第i-1个的字符拼接到result上，然后return result;

代码如下：

class Solution { public String longestCommonPrefix(String[] strs) { String result=""; int i=0,j; if(strs==null||strs.length==0) return result; if(strs.length==1) return strs[0]; Here:while(true){ for(j=1;j<strs.length;j++){ if(i>=strs[0].length() ||i>=strs[j].length() ||strs[0].charAt(i)!=strs[j].charAt(i)) break Here; } i++; } if(i-1>=0) result=result+strs[0].substring(0,i); return result; } }

LeetCode时间复杂度和空间复杂度分析如下 小结： 1、一开始strs[]只有一个元素的时候会进入到死循环，然后发现是如果不满足第二重循环的条件导致进不去的话就会一直卡在第一重循环的真循环里面，因为只能通过第二重循环来break，所以最后就在一开始加了if(strs.length==1) return strs[0];来防止这种情况 2、我发现有时候我的总思路是对的，但是实现的时候就会出一点小岔。。。 3、多个判断条件放在一个if语句中的时候一定要把判断是否越界的条件放在最前面，比如if(i>=strs[0].length() ||i>=strs[j].length() ||strs[0].charAt(i)!=strs[j].charAt(i))我就没有这样做然后越界了