BM84.最长公共前缀

1.问题描述

2.解决方案

思路：横向扫描
1.先计算出所有字符串最小长度minLen，作为while的边界，因为最长公共前缀就是最小长度
2.然后while使用point循环minLen-1次，每次循环都会对所有的字符串的point位置遍历，如果所有的point位置都相同就在结果集加上point位的字符，如果有一个不一样就break掉，返回

统计连通块技巧！连通块结束的时候统计！
每次循环都会对所有的字符串的point位置遍历，如果所有的point位置都相同就在结果集加上point位的字符，如果有一个不一样就break掉。实现角度是if(cur == pre&&i == strs.length-1) sb.append(cur); 如果是等于前一个字符并且是最后一个字符，说明point位置，所有字符串都相同了，这时候才会加到结果集中。

for(int i=1;i<strs.length;i++){char cur = strs[i].charAt(point);char pre = strs[i-1].charAt(point);if(cur!=pre){isBreak = false;break;}if(cur==pre&&i==strs.length-1) sb.append(cur);
}

代码实现

import java.util.*;public class Solution {public String longestCommonPrefix (String[] strs) {//1.if(strs.length==0) return "";if(strs.length==1) return strs[0]; int minLen = Integer.MAX_VALUE;for(String str : strs){minLen = Math.min(minLen, str.length());}//2.int point = 0;StringBuilder sb = new StringBuilder();while(point<=minLen-1){boolean isBreak = true;for(int i=1;i<strs.length;i++){char cur = strs[i].charAt(point);char pre = strs[i-1].charAt(point);if(cur!=pre){isBreak = false;break;}if(cur==pre&&i==strs.length-1) sb.append(cur);}if(!isBreak) break;point++;}return sb.toString();}
}