[刷题防痴呆] 0014 - 最长公共前缀 (Longest C

题目地址

https://leetcode.com/problems/longest-common-prefix/description/

题目描述

14. Longest Common Prefix

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.

思路

从第一个比到最后一个. 使用第一个数作为prefix, 然后直接比较, 不断更新prefix. 每次相比取substring. 如果中间出现完全不相等的, return "".

关键点

代码

• 语言支持：Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        String prefix = strs[0];
        
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            String cur = strs[i];
            while (j < prefix.length() && j < cur.length() 
                  && prefix.charAt(j) == cur.charAt(j)) {
                j++;
            }
            if (j == 0) {
                return "";
            }
            prefix = prefix.substring(0, j);
        }
        
        return prefix;
    }
}