LeetCode第十四题：最长公共前缀

admin
学习
2024-02-25
43热度
0评论

题目来源：最长公共前缀

1.题目描述

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

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

示例 1：

输入：strs = ["flower","flow","flight"]

输出："fl"

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

2.解题思路

解法一：横向扫描

描述：依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
参考代码：

java版：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        // 将公共前缀初始化为数字第一个元素
        String prefix = strs[0];
        // 遍历字符串数组
        for (int i = 1; i < strs.length; i++) {
            // 更新最长公共前缀
            prefix = commonPrefix(prefix, strs[i]);

            if (prefix.isEmpty()) {
                return "";
            }
        }
        return prefix;
    }

    // 求两个字符串的公共前缀
    private String commonPrefix(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);
    }
}

C++版：

class Solution {
public:
	string longestCommonPrefix(vector<string>& strs) {
		if (strs.empty()) return "";
		// 将公共前缀初始化为数组第一个元素
		string prefix = strs[0];
		// 遍历字符串数组
		for (int i = 1; i < strs.size(); i++) {
			// 更新最长公共前缀
			prefix = commonPrefix(prefix, strs[i]);

			if (prefix.empty()) return "";
		}
		return prefix;
	}

private:
	// 求两个字符串的公共前缀
	string commonPrefix(const string str1, const string str2) {
		// 取两个字符串短的作为循环结束条件
		int minLength = min(str1.length(), str2.length());

		int index = 0;
		// 两个字符串逐个字符比较
		while (index < minLength && str1[index] == str2[index])
		{
			index++;
		}

		return str1.substr(0, index);
	}
};

C版：

// 查找字符串数组中的最长公共前缀
char* longestCommonPrefix(char** strs, int strsSize) {
	if (strsSize == 0) return "";
	// 直接使用第一个字符串作为比较基准
	int prefixLen = strlen(strs[0]);

	for (int i = 1; i < strsSize; i++) {
		int j = 0;
		// 比较当前字符串与当前最长公共前缀
		while (j < prefixLen && strs[i][j] == strs[0][j]) {
			j++;
		}
		// 更新最长公共前缀的长度
		prefixLen = j;
		if (prefixLen == 0) {
			// 如果最长公共前缀长度为0，直接返回空字符串
			return "";
		}
	}

	// 创建足够容纳最长公共前缀及null终止符的字符串
	char* result = (char*)malloc(prefixLen + 1);
	if (result) {
		strncpy(result, strs[0], prefixLen);
		result[prefixLen] = '\0'; // 确保字符串以null终止
	}
	return result;
}

解法二：纵向扫描法

描述：它的基本原理是按列比较所有字符串的字符，从第一个字符开始，逐个向后比较每个字符串在该位置的字符。一旦在某个位置发现不匹配的字符，就可以立即停止比较，因为已经找到了所有字符串的最长公共前缀。
时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
参考代码：

java版：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";

        int minLength = Integer.MAX_VALUE;
        // 找到最短的字符串长度，因为最大前缀不会超过这个长度
        for (String str : strs)
            minLength = Math.min(minLength, str.length());

        // 纵向扫描，从数组第一个字符串第一个字符开始
        for (int i = 0; i < minLength; i++) {
            char currentChar = strs[0].charAt(i);
            // 把第一个字符串第i位的字符与数组中其他字符串的第i位进行比较
            for (int j = 1; j < strs.length; j++) {
                // 如果其他字符串的某个字符和第一个字符串的不相等了，就找到的最长前缀
                if (strs[j].charAt(i) != currentChar) {
                    return strs[0].substring(0, i);
                }
            }
        }
        // 如果所有字符串都被完全比较过，则最短字符串本身就是最长公共前缀
        return strs[0].substring(0, minLength);
    }
}

C++版：

class Solution {
public:
	string longestCommonPrefix(vector<string>& strs) {
		if (strs.empty()) return "";
		// 遍历第一个字符串的每一个字符
		for (int i = 0; i < strs[0].size(); i++) {
			char currentChar = strs[0][i];
			// 与剩余字符串对应位置的字符进行比较
			for (int j = 1; j < strs.size(); j++) {
				// 如果当前字符不等于对应位置的字符或当前字符串长度已达到当前索引i
				if (i == strs[j].size() || strs[j][i] != currentChar) {
					// 返回当前已找到的最长公共前缀
					return strs[0].substr(0, i);
				}
			}
		}
		// 如果所有字符串都被完全比较过，则第一个字符串本身就是最长公共前缀
		return strs[0];
	}
};

C版：

// 查找字符串数组中最短字符串的长度
int minStrLength(char **strs, int strsSize) {
    int minLength = strlen(strs[0]);
    for (int i = 1; i < strsSize; i++) {
        int len = strlen(strs[i]);
        if (len < minLength) {
            minLength = len;
        }
    }
    return minLength;
}

// 查找字符串数组中的最长公共前缀
char* longestCommonPrefix(char **strs, int strsSize) {
    if (strsSize == 0) return "";
    int minLength = minStrLength(strs, strsSize); // 获取最短字符串长度
    char *prefix = (char*)malloc(sizeof(char) * (minLength + 1)); // 分配内存
    if (!prefix) return NULL; // 内存分配失败

    for (int i = 0; i < minLength; i++) {
        char currentChar = strs[0][i]; // 获取第一个字符串的当前字符
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] != currentChar) {
                // 发现不匹配的字符，提前终止
                prefix[i] = '\0';
                return prefix;
            }
        }
        // 当前列的字符都匹配，将字符添加到结果中
        prefix[i] = currentChar;
    }

    prefix[minLength] = '\0'; // 确保字符串正确终止
    return prefix;
}

解法三：分治法

描述：分解：将原始的字符串数组分成两部分，左半部分和右半部分。解决：递归地在左半部分和右半部分分别找出最长公共前缀。合并：将左半部分和右半部分得到的最长公共前缀合并，即找到这两个公共前缀的公共部分。
时间复杂度：O(mn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。
空间复杂度：O(mlogn)，其中 m是字符串数组中的字符串的平均长度，n是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 log⁡n，每层需要 m 的空间存储返回结果。
参考代码：

java版：

class Solution {
        public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        return longestCommonPrefix(strs, 0, strs.length - 1);
    }

    // 分治法
    private String longestCommonPrefix(String[] strs, int left, int right) {
        // 如果左索引和右索引相同，返回数组当前索引的字符串
        if (left == right) {
            return strs[left];
        } else {
            // 否则，将数组一分为2，变成 left mid+1 right
            int mid = left + (right - left) / 2;
            // 求数组左边的最长公共前缀
            String lcpLeft = longestCommonPrefix(strs, left, mid);
            // 求数组右边的最长公共前缀
            String lcpRight = longestCommonPrefix(strs, mid + 1, right);
            // 返回左边和右边的最长公共前缀
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    // 求两个字符串的公共前缀
    private String commonPrefix(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);
    }
}

C++版：

class Solution {
public:
	string longestCommonPrefix(vector<string>& strs) {
		if (strs.empty()) return "";
		return longestCommonPrefix(strs, 0, strs.size() - 1);
	}

private:
	// 分治法
	string longestCommonPrefix(const vector<string>& strs, int left, int right) {
		// 如果左索引和右索引相同，返回数组当前索引的字符串
		if (left == right) {
			return strs[left];
		}
		else {
			// 否则，将数组一分为2，变成 left mid+1 right
			int mid = left + (right - left) / 2;
			// 求数组左边的最长公共前缀
			string lcpLeft = longestCommonPrefix(strs, left, mid);
			// 求数组右边的最长公共前缀
			string lcpRight = longestCommonPrefix(strs, mid + 1, right);
			// 返回左边和右边的最长公共前缀
			return commonPrefix(lcpLeft, lcpRight);
		}
	}

	// 求两个字符串的公共前缀
	string commonPrefix(const string str1, const string str2) {
		// 取两个字符串短的作为循环结束条件
		int minLength = min(str1.length(), str2.length());

		int index = 0;
		// 两个字符串逐个字符比较
		while (index < minLength && str1[index] == str2[index])
		{
			index++;
		}

		return str1.substr(0, index);
	}
};

C版：

char* longestCommonPrefix(char** strs, int strsSize);
char* divideAndConquer(char** strs, int left, int right);
char* findCommonPrefix(char* str1, char* str2);

// 查找字符串数组中的最长公共前缀
char* longestCommonPrefix(char** strs, int strsSize) {
	if (strsSize == 0) return "";
	return divideAndConquer(strs, 0, strsSize - 1);
}

// 分治法核心逻辑
char* divideAndConquer(char** strs, int left, int right) {
	// 当左右边界相等时，直接返回当前字符串
	if (left == right) {
		// 需要复制字符串以避免修改原始数据
		char* str = (char*)malloc(strlen(strs[left]) + 1);
		strcpy(str, strs[left]);
		return str;
	}
	else {
		int mid = left + (right - left) / 2;
		char* lcpLeft = divideAndConquer(strs, left, mid); // 左侧最长公共前缀
		char* lcpRight = divideAndConquer(strs, mid + 1, right); // 右侧最长公共前缀
		char* lcp = findCommonPrefix(lcpLeft, lcpRight); // 合并左右两侧的结果
		free(lcpLeft); // 释放左侧结果字符串的内存
		free(lcpRight); // 释放右侧结果字符串的内存
		return lcp;
	}
}

// 查找两个字符串的公共前缀
char* findCommonPrefix(char* str1, char* str2) {
	int minLength = strlen(str1) < strlen(str2) ? strlen(str1) : strlen(str2);
	char* commonPrefix = (char*)malloc(minLength + 1); // 分配足够的内存
	for (int i = 0; i < minLength; i++) {
		if (str1[i] != str2[i]) {
			commonPrefix[i] = '\0'; // 遇到不同字符，提前终止
			return commonPrefix;
		}
		commonPrefix[i] = str1[i]; // 复制相同的字符
	}
	commonPrefix[minLength] = '\0'; // 确保字符串正确终止
	return commonPrefix;
}

解法四：二分查找

描述：初始化搜索范围：首先确定所有字符串中最短字符串的长度minLen，因为最长公共前缀的长度不会超过这个长度。这就设定了二分查找的上界。二分搜索：通过二分法在0到minLen的范围内搜索，每次取中间值mid作为假定的公共前缀长度。验证中间值：检查所有字符串是否拥有长度为mid的公共前缀。这通过比较每个字符串的前mid个字符是否相同来实现。调整搜索范围：如果所有字符串都有长度为mid的公共前缀，则将搜索范围调整到较大的一半，即mid+1到minLen；否则，调整到较小的一半，即0到mid-1。确定最长公共前缀：重复步骤2到4，直到找到最大的mid，使得所有字符串都有长度为mid的公共前缀。
时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是 O(log⁡m)，每次迭代最多需要比较 mn个字符，因此总时间复杂度是 O(mnlog⁡m)。
空间复杂度：O(1)。使用的额外空间复杂度为常数。
参考代码：

java版：

class Solution{
public String longestCommonPrefix(String[] strs) {
        // 处理边界情况：数组为空或长度为0时，返回空字符串
        if (strs == null || strs.length == 0)
            return "";
        // 找到字符串数组中最短字符串的长度，因为最长公共前缀的长度不会超过这个长度
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }
        // 初始化二分查找的范围
        int low = 1;
        int high = minLen;
        while (low <= high) {
            // 计算中点，尝试作为公共前缀的长度
            int mid = (low + high) / 2;
            // 检查当前长度是否是所有字符串的公共前缀
            if (isCommonPrefix(strs, mid)) {
                // 如果是，说明公共前缀至少为mid，向右半区间查找
                low = mid + 1;
            } else {
                // 如果不是，说明公共前缀小于mid，向左半区间查找
                high = mid - 1;
            }
        }
        // 二分查找结束后，high和low会错开，实际的最大公共前缀长度为(high + low) / 2
        return strs[0].substring(0, (low + high) / 2);
    }

    // 辅助函数，用于检查字符串数组是否有长度为len的公共前缀
    private boolean isCommonPrefix(String[] strs, int len) {
        // 获取第一个字符串的前len个字符作为基准
        String str1 = strs[0].substring(0, len);
        // 遍历数组中的其他字符串
        for (int i = 1; i < strs.length; i++) {
            // 如果当前字符串不以str1为前缀，则说明len不是公共前缀的长度
            if (!strs[i].startsWith(str1)) {
                return false;
            }
        }
        // 如果所有字符串都以str1为前缀，则说明len是公共前缀的长度
        return true;
    }
}

C++版：

class Solution {
public:
	// 主函数，用于查找字符串数组中的最长公共前缀
	string longestCommonPrefix(vector<string>& strs) {
		// 处理空数组的情况
		if (strs.empty()) return "";
		// 找到字符串数组中最短字符串的长度，因为最长公共前缀的长度不会超过这个长度
		int minLen = INT_MAX;
		for (const string& str : strs) {
			minLen = min(minLen, static_cast<int>(str.size()));
		}
		// 初始化二分查找范围
		int low = 1;
		int high = minLen;

		while (low <= high) {
			// 计算中点，尝试作为公共前缀的长度
			int mid = (low + high) / 2;
			// 检查当前长度是否是所有字符串的公共前缀
			if (isCommonPrefix(strs, mid)) {
				// 如果是，说明公共前缀至少为mid，向右半区间查找
				low = mid + 1;
			}
			else {
				// 如果不是，说明公共前缀小于mid，向左半区间查找
				high = mid - 1;
			}
		}
		// 二分查找结束后，high和low会错开，实际的最大公共前缀长度为(high + low) / 2
		return strs[0].substr(0, (low + high) / 2);
	}

private:
	// 辅助函数，用于检查字符串数组是否有长度为len的公共前缀
	bool isCommonPrefix(const vector<string>& strs, int len) {
		// 获取第一个字符串的前len个字符作为基准
		string prefix = strs[0].substr(0, len);
		// 遍历数组中的其他字符串
		for (int i = 1; i < strs.size(); i++) {
			for (int j = 0; j < len; j++) {
				// 如果任何字符不匹配，说明当前长度不是公共前缀
				if (strs[i][j] != prefix[j]) {
					return false;
				}
			}
		}
		// 所有字符串在长度为len的前缀上都匹配
		return true;
	}
};

C版：

// 函数声明：检查是否存在长度为len的公共前缀
int isCommonPrefix(char** strs, int strsSize, int len) {
    for (int i = 1; i < strsSize; i++) {
        for (int j = 0; j < len; j++) {
            // 如果当前字符不匹配或已经超过某个字符串的长度，返回0
            if (strs[0][j] != strs[i][j]) {
                return 0;
            }
        }
    }
    // 所有字符串在长度为len的前缀上都匹配
    return 1;
}

// 主函数：查找字符串数组中的最长公共前缀
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";

    // 找到所有字符串中的最短长度
    int minLen = INT_MAX;
    for (int i = 0; i < strsSize; i++) {
        int len = strlen(strs[i]);
        if (len < minLen) {
            minLen = len;
        }
    }

    // 初始化二分查找范围
    int low = 0;
    int high = minLen;
    while (low <= high) {
        int mid = (low + high) / 2; // 计算中点
        if (isCommonPrefix(strs, strsSize, mid)) {
            // 如果当前长度是公共前缀，尝试更长的长度
            low = mid + 1;
        } else {
            // 如果当前长度不是公共前缀，尝试更短的长度
            high = mid - 1;
        }
    }

    // 二分查找结束后，最长公共前缀的长度为high
    char* prefix = (char*)malloc(sizeof(char) * (high + 1));
    strncpy(prefix, strs[0], high);
    prefix[high] = '\0'; // 确保字符串以null终止
    return prefix;
}