14. 最长公共前缀

题目链接

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

说明:

所有输入只包含小写字母 a-z 。

示例 1

输入: ["flower","flow","flight"]
输出: "fl"

示例 2

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

题解

public String longestCommonPrefix(String[] strs) {
	if (strs.length < 1) {
		return "";  // 数组长度小于1,直接返回默认值
	}
	StringBuilder stringBuilder = new StringBuilder();
	int minLength = Integer.MAX_VALUE;
	for (String str : strs) {
		if (str.length() == 0) {
			return "";  // 其中一个字符串长度为0,直接返回默认值
		}
		if (str.length() < minLength) {
			minLength = str.length();
		}
	}

	for (int i = 0; i < minLength; i++) {
		char prefix = strs[0].charAt(i);
		boolean flag = true;
		for (String str : strs) {
			if (str.charAt(i) != prefix) {
				flag = false;
			}
		}
		if (flag) {
			stringBuilder.append(prefix);
		} else {
			break;
		}
	}
	if (stringBuilder.toString().length() > 0) {
		return stringBuilder.toString();
	} else {
		return "";
	}
}

复杂度分析

  • 时间复杂度:$O(n^2)$。
  • 空间复杂度:$O(1)$。

手记

遍历即可,注意特殊值的影响,提前排除特殊情况即可。