（Java）leetcode-14 Longest Common Prefix

我不是女神ヾ 2022-02-24 03:56 140阅读 0赞

【最长公共前缀】

# 题目 #

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

Input: ["flower","flow","flight"]
    Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
    Output: ""

Explanation: There is no common prefix among the input strings.  
Note:

All given inputs are in lowercase letters a-z.

# 思路 #

将数组中的第一个串(pre)去对比后面的串，看是否pre为后面字符串的前缀，若不是，则减少pre的长度（从末尾的字符删起），直到pre成为后面串的前缀为止。当检查完一个子串后继续检查后面的子串，最后pre将成为公共的前缀。  
时间复杂度：O(s) s为所以字符串的总字符数  
空间复杂度：O(1)

# 代码 #

ps: `strs[i].indexOf(pre)`在没有检索到相应目标时返回的是-1，若返回0说明pre是strs\[i\]的前缀。

class Solution { 
    	   public String longestCommonPrefix(String[] strs) { 
    	    if(strs == null || strs.length == 0)    return "";
    	    String pre = strs[0];
    	    int i = 1;
    	    while(i < strs.length){ 
    	        while(strs[i].indexOf(pre) != 0) //只要pre不出现在该串的首尾
    	            pre = pre.substring(0,pre.length()-1);//去掉pre的最后一位重新检测
    	        i++;
    	    }
    	    return pre;
    	}
    }

## 提交结果 ##

Runtime: 3 ms, faster than 92.12% of Java online submissions for Longest Common Prefix.  
Memory Usage: 38.9 MB, less than 17.51% of Java online submissions for Longest Common Prefix.