Example
最长公共前缀
题目概述：编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
解题思路：用表示字符串
表示字符串的最长公共前缀。
可以得到以下结论：
基于该结论，可以得到一种查找字符串数组中的最长公共前缀的简单方法。依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
其主要思想如下图所示。
解题步骤：
1. 首先判断给定的字符串数组是否为null或长度是否为0，若是则公共前缀一定为””，将””返回。
2. 基于解题思路，第一步将S1与S2进行比较，求公共前缀prefix，而后将prefix依次与后续字符串比较。因此首先将S1作为默认公共前缀，这样整个操作流程变为将公共前缀prefix(默认为S1)依次与S2开始的字符串相比较，生成新的公共前缀prefix，进行下一轮比较。每次比较结束后，若新的公共前缀prefix长度为0，说明不存在公共前缀，即公共前缀为””，则退出循环，将此prefix返回。否则说明比较到当前仍存在公共前缀prefix，继续遍历。
3. 遍历结束后，将公共前缀prefix返回。
4. 解题中用到的两个字符串比较，求公共前缀的方法如下：①求两个字符串长度的最小值length，作为遍历每个字符串中字符的最大个数。②定义变量index，作为截取子串的索引位置，初始值为0。③定义循环，从初始0索引开始遍历，若当前索引位置小于length且两个字符串的当前索引位置的字符相等，则将变量index自加一，继续考察下一个索引位置，否则说明索引超出长度最小的字符串的区间，考察完毕，或者取出的两个字符不相等，跳出循环。④将str1（或str2）的0索引至index索引之间的子串（左闭右开）截取出来，即为两个字符串的最大公共前缀，将其返回。
示例代码如下：
public class LongestCommonPrefix { /** * 编写一个函数来查找字符串数组中的最长公共前缀。 * 如果不存在公共前缀，返回空字符串 ""。 * 示例 1： * 输入：strs = ["flower","flow","flight"] * 输出："fl" * 示例 2： * 输入：strs = ["dog","racecar","car"] * 输出："" * 解释：输入不存在公共前缀。 */ public static void main(String[] args) { LongestCommonPrefix lcp = new LongestCommonPrefix(); System.out.println(lcp.longestCommonPrefix(new String[]{"flower", "flow", "flight"})); // fl } /** * 官方 * * @param strs * @return */ public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } String prefix = strs[0]; int count = strs.length; for (int i = 1; i < count; i++) { prefix = longestCommonPrefix(prefix, strs[i]); if (prefix.length() == 0) { break; } } return prefix; } public String longestCommonPrefix(String str1, String str2) { int length = Math.min(str1.length(), str2.length()); int index = 0; while (index < length && str1.charAt(index) == str2.charAt(index)) { index++; } return str1.substring(0, index); } }
