📢前言
🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
🌲 今天是力扣算法题持续打卡第10天🎈！
🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲原题样例
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。
示例 1： 输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2： 输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
提示：
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] 仅由小写英文字母组成
🌻C#方法一：横向扫描
思路解析
代码
public class Solution { 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.Substring(index,1) == str2.Substring(index,1)) { index++; } return str1.Substring(0, index); } }
执行结果
通过 执行用时：96 ms，在所有 C# 提交中击败了82.77%的用户 内存消耗：27.1 MB，在所有 C# 提交中击败了13.42%的用户
复杂度分析
时间复杂度：O( n)，其中 n 是字符串 s 的长度。 空间复杂度：O(1)
🌻Java方法：横向扫描
解题思路
代码
class Solution { 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); } }
执行结果
通过 执行用时：0 ms，在所有 Java 提交中击败了100%的用户 内存消耗：36.5 MB，在所有 Java 提交中击败了48.02%的用户
复杂度分析
时间复杂度：O(mn)O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。 空间复杂度：O(1)O(1)。使用的额外空间复杂度为常数。
这里其实还有一种解题思路
既然要比较最长公共前缀，那我们只需要先将给定的字符串列表按照长度排序
只需要比较最长的和最短的两个字符串有没有公众前缀即可
因为最长的公共前缀也不过是给定字符串中最短的那一个！
💬总结
今天是力扣算法题打卡的第十天！
文章采用 C# 和 Java 两种编程语言进行解题
有时候一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
那今天的算法题分享到此结束啦，明天再见！
