淘宝网站首页怎么做,建设网站服务器怎么选,肥城住房和城乡建设局网站,网站ftp密码题目描述
给你一个大小为 n 的字符串数组 strs #xff0c;其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀#xff0c;返回这个公共前缀。
数据范围#xff1a; 数据范围:0n5000#xff0c;0len(strsi) 5000 进阶:空间复杂度 O(1)其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀返回这个公共前缀。
数据范围 数据范围:0n50000len(strsi) 5000 进阶:空间复杂度 O(1)时间复杂度 O(n*len)
示例1
输入[“abca”,“abc”,“abca”,“abc”,“abcc”] 返回值“abc”
示例2
输入[“abc”] 返回值“abc”
解题思路
方法一水平扫描法 初始化首先检查输入数组是否为空如果为空则直接返回空字符串。如果只有一个字符串则返回该字符串本身因为这时最长公共前缀就是这个字符串。 迭代比较将第一个字符串作为初始的最长公共前缀。然后遍历数组中的其他字符串对每个字符串使用indexOf方法检查当前公共前缀是否存在于该字符串中。 缩短当前公共前缀如果发现当前公共前缀不在某个字符串中就将公共前缀缩短一个字符再次检查。这个过程一直持续到找到所有字符串共有的前缀或者为空字符串。 返回结果最后返回找到的最长公共前缀。
方法一JavaScript版本代码如下
function longestCommonPrefix(strs) {// 如果数组为空直接返回空字符串if (strs.length 0) return ;// 如果数组只有一个元素返回该元素本身if (strs.length 1) return strs[0];// 初始化最长公共前缀为第一个字符串let prefix strs[0];// 遍历数组中的每个字符串从第二个开始for (let i 1; i strs.length; i) {// 当前字符串与前缀不匹配时缩短当前前缀while (strs[i].indexOf(prefix) ! 0) {// 缩短前缀字符串prefix prefix.substring(0, prefix.length - 1);// 如果前缀为空说明没有公共前缀返回空字符串if (prefix ) return ;}// 当前字符串匹配前缀继续检查下一个字符串}// 返回找到的最长公共前缀return prefix;
}// 示例
console.log(longestCommonPrefix([abca, abc, abca, abc, abcc])); // abc
console.log(longestCommonPrefix([abc])); // abc方法二垂直扫描法 初始化同样检查输入数组是否为空如果为空则直接返回空字符串。 逐列比较遍历第一个字符串的每个字符将这些字符与其他字符串在相同位置的字符进行比较。 构建公共前缀如果在某个位置所有字符串的字符都相同则将该字符添加到公共前缀中。如果在某个位置发现字符不匹配或某个字符串长度不足则停止比较并返回当前的公共前缀。 返回结果最后返回构建好的最长公共前缀。
方法二JavaScript版本代码如下
function longestCommonPrefix(strs) {// 如果数组为空直接返回空字符串if (strs.length 0) return ;// 初始化最长公共前缀为空字符串let prefix ;// 遍历第一个字符串的每个字符for (let j 0; j strs[0].length; j) {// 获取第一个字符串的当前字符const char strs[0][j];// 遍历数组中的其他字符串for (let i 1; i strs.length; i) {// 如果当前字符不在其他字符串的相同位置或者当前字符串长度不足if (j strs[i].length || strs[i][j] ! char) {// 没有公共前缀返回当前已找到的公共前缀return prefix;}}// 如果所有字符串在当前位置都有相同的字符将该字符添加到公共前缀prefix char;}// 返回找到的最长公共前缀return prefix;
}// 示例
console.log(longestCommonPrefix([abca, abc, abca, abc, abcc])); // abc
console.log(longestCommonPrefix([abc])); // abc相同测试用例方法一和方法二的运行效果对比如下图可看出两个方法占用内存差不太多但方法二的运行时间比方法一更高效一些。
总结与类似题解题思路
以上两个方法都实现了寻找字符串数组中最长公共前缀的功能。方法一通过逐个字符串进行水平扫描来缩短前缀而方法二通过逐字符垂直扫描来构建前缀。两种方法都有其适用场景但方法二在时间和空间复杂度上通常更优。
对于求解最长公共前缀这类问题核心思路是逐步缩小问题的规模直到找到所有字符串共有的前缀或者确定没有公共前缀为止。具体实现时可以采用以下策略 初始化总是先检查输入数组是否为空或只有一个元素这些情况下可以直接返回相应结果。 迭代或递归通过迭代或递归的方式逐步缩小问题的规模。在迭代中可以通过缩短当前公共前缀水平扫描法或逐列比较字符垂直扫描法来实现。 比较与更新在每一步中都需要比较当前公共前缀与新的字符串或字符根据比较结果更新公共前缀。 结束条件当发现公共前缀为空或者已经比较到某个字符串的末尾时就可以停止进一步的搜索并返回当前的公共前缀。
对于类似的题目比如求多个区间的交集、求多个数组的交集等都可以采用类似的思路逐步缩小问题的规模通过比较和更新来找到共有部分直到无法再找到共有部分为止。这种思路的关键在于找到合适的数据结构和方法来高效地进行比较和更新操作。
