[Java·算法·简单] LeetCode 14. 最长公共前缀 详细解读

题目

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

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

示例

示例1

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

输出："fl"

示例2

输入：strs = ["dog","racecar","car"]

输出：""

解释：输入不存在公共前缀。

提示 ：

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

👉️ 力扣原文

class Solution {
    public String longestCommonPrefix(String[] strs) {
       if(strs.length == 0){
           return "";
       }
 
       String ans=strs[0];
       for(int i=1;i<strs.length;i++){
           int j=0;
           for(;j<ans.length() && j<strs[i].length();j++){
               if(ans.charAt(j) != strs[i].charAt(j))
                    break;           
                }
               ans = ans.substring(0, j);
               if(ans.equals(""))
                    return ans;
           
           }
           return ans;
       }     
}

详细解读

这段代码实现了一个寻找字符串数组中最长公共前缀的算法。下面是这个算法的解读：

1. **初始化最长公共前缀：**首先，将最长公共前缀初始化为第一个字符串strs[0]。
2. **遍历字符串数组：**从第二个字符串开始遍历数组。
3. **比较字符：**对于当前的字符串strs[i]，从第一个字符开始，与最长公共前缀ans逐个字符比较。
4. **截取最长公共前缀：**如果在某一位置发现字符不匹配，则将最长公共前缀ans截取到不匹配位置，保留前面匹配的部分。
5. **更新最长公共前缀：**将截取后的最长公共前缀ans更新为当前的最长公共前缀。
6. **重复步骤3-5：**继续遍历字符串数组中的下一个字符串，重复比较和更新步骤，直到遍历完所有字符串或者发现最长公共前缀为空字符串。
7. **返回结果：**返回最终得到的最长公共前缀ans。

该算法的时间复杂度为O(n*m)，其中n是字符串数组的长度，m是最长公共前缀的长度。