今日题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成
思路
公共最长前缀的特点： 前缀必然存在每一个字符串。
使用第一个字符串与其他字符串进行逐一对比得出前缀长度；并且所有长度取最小值就是题解
可优化的点：
- 公共前缀不会超过任意一个字符串的长度，不用每次都比较整个字符串，只要比较当前的前缀长度即可
- 如果没有公共前缀，那么不需要遍历剩余的字符串
实现
public String longestCommonPrefix(String[] strs) { if (strs.length == 0) { return ""; } // 最长前缀末尾位置 int end = strs[0].length() - 1; for (int i = 1; i < strs.length; i++) { // 优化1: 不用比较整个字符串, 只要比较前缀长度即可 int j = 0; for (; j <= end && j < strs[i].length(); j++) { if (strs[0].charAt(j) != strs[i].charAt(j)) { //如果第一个字符都不相等，就不用比较了 if(j == 0){ return ""; } break; } } end = Math.min(end, j - 1); } return strs[0].substring(0, end + 1); }
执行用时：1 ms, 在所有 Java 提交中击败了70.59%的用户
内存消耗：36.3 MB, 在所有 Java 提交中击败了89.59%的用户
解法二
第二种解法其实和第一种是一样的思想，只不过可以利用String的api方法
startWith()方法，有了这个方法可以使代码实现更加优雅
public String longestCommonPrefix(String[] strs) { if (strs.length == 0) { return ""; } // 最长前缀 String commonPrefix = strs[0]; for (int i = 1; i < strs.length; i++) { while (!strs[i].startsWith(commonPrefix)) { if (commonPrefix.length() == 0) { return ""; } commonPrefix = commonPrefix.substring(0, commonPrefix.length() - 1); } } return commonPrefix; }
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.5 MB, 在所有 Java 提交中击败了44.26%的用户
小结
这两天的题目相对来说比较简单，但是能够一次完全写对还是有难度的，需要多注意常用的api写法
比如：
- map的循环方式，entry的写法
- String的常用api，比如substring(start, end)注意不是驼峰, 区间是左闭右开**[start, end)**
- 字符串和链表获取串长度是方法ss.length()，而数组的是变量array.length
- 数字与字符串之间的互转，String.valueOf(int), Integer.parseIn(string)这个方法不会频繁拆箱装箱
- 而且做题有注意审题，这道题我刚开始还以为是找最长公共子串
今天多学一点知识，明天就少说一句求人的话
