Longest Common Prefix

                                            
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) {
            return "";
        }
        
        string prefix = strs[0];
        
        for (int i = 1; i < strs.size(); i++) {
            while (strs[i].find(prefix) != 0) {
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) {
                    return "";
                }
            }
        }
        
        return prefix;
    }
};

                                            
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++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        
        return prefix;
    }
}

                                            
class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        
        strs.sort()
        
        prefix = ""
        for i in range(len(strs[0])):
            if strs[0][i] == strs[-1][i]:
                prefix += strs[0][i]
            else:
                break
        
        return prefix

                                            
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) {
        return "";
    }
    
    int i, j;
    for (i = 0; i < strlen(strs[0]); i++) {
        for (j = 1; j < strsSize; j++) {
            if (strs[j][i] != strs[0][i] || strs[j][i] == '\0') {
                char* result = (char*)malloc(sizeof(char) * (i+1));
                strncpy(result, strs[0], i);
                result[i] = '\0';
                return result;
            }
        }
    }
    
    return strs[0]; // if input array is empty or contains only 1 element
}

                                            
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) {
        return "";
    }
    
    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
        }
        if (prefix === "") {
            break;
        }
    }
    
    return prefix;
};

                                            
function longestCommonPrefix(strs: string[]): string {
    if (strs.length === 0) return "";
    
    let prefix = "";
    for (let i = 0; i < strs[0].length; i++) {
        const char = strs[0][i];
        for (let j = 1; j < strs.length; j++) {
            if (i === strs[j].length || strs[j][i] !== char) {
                return prefix;
            }
        }
        prefix += char;
    }
    
    return prefix;
};

                                            
class Solution {
    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        if (empty($strs)) {
            return "";
        }
        
        $prefix = $strs[0];
        
        for ($i = 1; $i < count($strs); $i++) {
            while (strpos($strs[$i], $prefix) !== 0) {
                $prefix = substr($prefix, 0, -1);
                if (empty($prefix)) {
                    return "";
                }
            }
        }
        
        return $prefix;
    }
}

                                            
class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        guard let firstStr = strs.first else {
            return ""
        }
        
        var prefix = ""
        for (i, char) in firstStr.enumerated() {
            for str in strs.dropFirst() {
                if i >= str.count || str[str.index(str.startIndex, offsetBy: i)] != char {
                    return prefix
                }
            }
            prefix.append(char)
        }
        
        return prefix
    }
}

                                            
class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        if (strs.isEmpty()) {
            return ""
        }
        
        var prefix = strs[0]
        for (i in 1 until strs.size) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length - 1)
                if (prefix.isEmpty()) {
                    return ""
                }
            }
        }
        
        return prefix
    }
}

                                            
class Solution {
  String longestCommonPrefix(List<String> strs) {
    if (strs.isEmpty) {
      return "";
    }

    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
      while (strs[i].indexOf(prefix) != 0) {
        prefix = prefix.substring(0, prefix.length - 1);
        if (prefix.isEmpty) {
          return "";
        }
      }
    }
    return prefix;
  }
}

                                            
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    prefix := strs[0]
    for i := 1; i < len(strs); i++ {
        for strings.Index(strs[i], prefix) != 0 {
            prefix = prefix[:len(prefix)-1]
            if prefix == "" {
                return ""
            }
        }
    }
    return prefix
}

                                            
# @return {String}
def longest_common_prefix(strs)
    return "" if strs.empty?
    
    prefix = strs.min_by(&:length)
    
    strs.each do |str|
        prefix = prefix.chop until str.start_with?(prefix)
    end
    
    prefix
end

                                            
impl Solution {
    pub fn longest_common_prefix(strs: Vec<String>) -> String {
        if strs.is_empty() {
            return String::new();
        }
        
        let mut prefix = strs[0].clone();
        
        for i in 1..strs.len() {
            while !strs[i].starts_with(&prefix) {
                prefix.pop();
            }
        }
        
        prefix
    }
}

To solve this coding challenge, we need to find the longest common prefix amongst an array of strings. A common prefix is a substring that appears at the beginning of each string in the array. If there is no common prefix, we should return an empty string.

Explanation

Input constraints : We are given an array of strings, and we need to consider the constraints where the array has a length between 1 and 200, and each string's length is between 0 and 200. The strings consist only of lowercase English letters.
Example 1 : For the input
["flower","flow","flight"]

, the longest common prefix is
"fl"

because this is the substring that appears at the beginning of each string.
Example 2 : For the input
["dog","racecar","car"]

, there is no common prefix, so the output is an empty string
""

.

To determine the longest common prefix, we can use a series of steps involving sorting the array and comparing characters between the first and the last string in the sorted array. Sorting the array is effective because:

After sorting, the strings that are lexicographically closest to each other will be adjacent in the sorted array. Therefore, the common prefix of the entire array will be the common prefix of the first and the last string in the sorted array.
By comparing only the first and last strings, we significantly reduce the number of comparisons needed.

Detailed Steps in Pseudocode

Check if the input array is empty : If the array
strs

is empty, return an empty string.
Sort the array
strs

: Sorting the array helps to bring the strings with common prefixes closer together. After sorting, the common prefix for the entire array needs to be found by comparing just the first and the last string in the sorted array.
Initialize an empty string for the common prefix : Define a variable
prefix

to keep track of the common prefix characters.
Compare the characters of the first and last string in the sorted array : Loop through the characters of the first string in the sorted array. For each character, check if it matches the corresponding character in the last string.
Build the common prefix : If the characters match, append the character to the
prefix

variable. If they don't match, break out of the loop since the common prefix ends there.
Return the common prefix : Finally, return the variable
prefix

which contains the longest common prefix.

Let's put this into pseudocode with comments:

                                            
# Check if the input array is empty
if array_of_strings is empty
    return empty string

# Sort the array of strings
sort array_of_strings

# Initialize an empty string for the common prefix
common_prefix = ""

# Compare characters of the first and the last string in the sorted array
for each index in range of length of the first string in array_of_strings
    # If characters of the first and last string match at the current index
    if first string's character at current index == last string's character at current index
        # Append the character to the common prefix
        common_prefix = common_prefix + first string's character at current index
    else
        # Break out of the loop if characters don't match
        break

# Return the common prefix
return common_prefix

By following the above steps, the algorithm efficiently determines the longest common prefix by leveraging string sorting and character comparison, ultimately ensuring that the solution is both simple and effective.