LeetCode 14. Longest Common Prefix

Description

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

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.

Explanation

To find the longest common prefix string amongst an array of strings, we can declare a variable “longestCommonPrefix”. In the beginning, it initializes with the value of the first string of the input array. Then compare the “longestCommonPrefix” with all strings in the array to get the longest common prefix for all the strings.

Java Solution

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

Python Solution

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        longest_prefix = ""
        
        if strs is None or len(strs) == 0:
            return longest_prefix

        if len(strs) == 1:
            return strs[0]
            
        first_word = strs[0]
                
        for i in range(0, len(first_word) + 1):
            prefix = first_word[0: i]

            should_update_longest = True
                       
            for another_word in strs[1:]:
                if (another_word[0: i] != prefix):
                    should_update_longest = False
                    break
            
            if should_update_longest:
                longest_prefix = prefix           
            else:
                break

        return longest_prefix