知名中文网站建设,设计师服务平台鱼巴士官网,阿里云建wordpress,长春哪家互联网做得好大家好#xff0c;我是怒码少年小码。
最长公共前缀
LeetCode 14#xff1a;编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀#xff0c;返回空字符串 “”。 示例#xff1a; 输入#xff1a;strs [“flower”,“flow”,“flight”]输出#xff…大家好我是怒码少年小码。
最长公共前缀
LeetCode 14编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 “”。 示例 输入strs [“flower”,“flow”,“flight”]输出“fl” 方法一
分析最先想到的应该就是选择一个字符串作为基点和之后的字符串逐个比较了就像竖向比较一样 代码如下 这段代码实现了一个函数 longestCommonPrefix用于找出一组字符串中最长的公共前缀。下面对代码进行详细解释
string longestCommonPrefix(vectorstring strs) {if(!strs.size()){return ;}int length strs[0].size();int count strs.size();for(int i0 ; i length;i){char c strs[0][i];for(int j 1;jcount;j){if(istrs[j].size() || strs[j][i] ! c){return strs[0].substr(0,i);}}}return strs[0];
}if(!strs.size())首先代码检查传入的字符串向量 strs 是否为空。如果为空则直接返回一个空字符串因为没有任何字符串需要进行比较与查找公共前缀。int length strs[0].size();接下来代码获取第一个字符串的长度作为 length 变量的值以确定最长公共前缀的最大可能长度。int count strs.size();获取传入的字符串向量 strs 的大小表示包含的字符串数量。for(int i0 ; i length;i)这是一个外层循环用于遍历第一个字符串的字符。char c strs[0][i];获取第一个字符串的第 i 个字符并将其存储在变量 c 中作为待比较的字符。for(int j 1;jcount;j)这是一个内层循环用于遍历除第一个字符串之外的其他所有字符串。if(istrs[j].size() || strs[j][i] ! c)在每次循环内部首先判断索引 i 是否已经超出某个字符串的长度或者当前字符串的第 i 个字符与第一个字符串的第 i 个字符是否相等。 如果索引 i 已经超出了某个字符串的长度或者当前字符串的第 i 个字符与第一个字符串的第 i 个字符不相等表示已经找到了最长公共前缀的结束位置即当前索引 i 的位置。此时函数使用 substr(0,i) 返回第一个字符串的前 i 个字符作为最长公共前缀。否则继续比较下一个字符串的第 i 个字符。 如果没有在内层循环中返回最长公共前缀说明第一个字符串是所有字符串的公共前缀因此返回第一个字符串即可。
substr(0, i) 是一个字符串的成员函数用于提取从索引 0 开始长度为 i 的子字符串。在这段代码中如果找到了最长公共前缀的结束位置索引 i函数使用 substr(0,i) 来提取第一个字符串的前 i 个字符作为最长公共前缀。
方法二
分析先找到数组中前两个字符串的最长公共前缀然后再比较第二个字符串和第三个字符串的最长公共前缀看看是否需要缩小直到数组遍历完毕或者最长公共前缀已经为零了。 代码我使用Java写的 public String longestCommonPrefix(String[] strs) {if(strs null || strs.length 0){return ;}String prefix strs[0];int count strs.length;for(int i 1;icount;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 i 0;while(ilength str1.charAt(i) str2.charAt(i)){i;}return str1.substring(0,i);}首先代码判断了输入参数是否为空或数组长度是否为0如果是则返回空字符串。接下来定义了一个变量prefix并将其初始化为数组的第一个字符串作为初始化前缀。同时定义了一个计数变量count将其赋值为数组的长度。
然后通过一个循环遍历数组中的每个字符串从第二个字符串开始将当前前缀和当前字符串传递给另一个方法longestCommonPrefix获取新的前缀。在这个方法中代码首先计算了两个字符串的最小长度因为最长公共前缀不能超过这个最小长度。
然后通过一个while循环从字符串的第一个字符开始逐个比较两个字符串的字符是否相等直到遇到不相等的字符或达到最小长度为止。循环结束后返回前缀字符串它就是两个字符串的最长公共前缀。
longestCommonPrefix(String[] strs)方法中每次获取了新的前缀后代码会判断新的前缀的长度是否为0如果是则终止循环。最后返回最终的前缀作为结果。
它的时间复杂度是O(n*m)其中n是字符串的平均长度m是数组中字符串的数量。
