algoadvance

Leetcode 14. Longest Common Prefix

Problem Statement

The problem is to write a function to find the longest common prefix string among an array of strings. If there is no common prefix, return an empty string “”.

Example:

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

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Clarifying Questions

  1. What is the expected output for an array containing only one string?
    • For example, ["flower"]?
    • Output: The single string itself, “flower”.
  2. Should we handle the edge case of an empty array?
    • Yes. If the input array is empty, the function should return an empty string "".
  3. What is the maximum size of the input array (number of strings), and the length of each string?
    • Let’s assume typical constraints: the number of strings (n) could be up to 200 and the length of each string (m) could be up to 200 characters.

Strategy

  1. Edge Cases Handling:
    • If the array is empty, return an empty string.
    • If the array has only one string, return that string directly.
  2. Prefix Comparison Strategy:
    • Start by assuming the first string in the array is the common prefix.
    • Iterate through the remaining strings and compare each string to the current common prefix.
    • Update the common prefix by comparing each character until there’s a mismatch.
    • If the common prefix becomes an empty string during the comparison, terminate as there’s no common prefix.
  3. Implementation Steps:
    • Initialize common prefix with the first string.
    • Iterate through each character of each subsequent string to update the common prefix.
    • Return the common prefix after processing all strings.

Code

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        // Start with the first string as the common prefix.
        String commonPrefix = strs[0];
        
        for (int i = 1; i < strs.length; i++) {
            commonPrefix = findCommonPrefix(commonPrefix, strs[i]);
            if (commonPrefix.isEmpty()) {
                break;
            }
        }
        
        return commonPrefix;
    }
    
    // Helper method to find common prefix between two strings
    private String findCommonPrefix(String str1, String str2) {
        int minLength = Math.min(str1.length(), str2.length());
        int i = 0;
        while (i < minLength && str1.charAt(i) == str2.charAt(i)) {
            i++;
        }
        return str1.substring(0, i);
    }
    
    // Main method for testing purposes
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        String[] strs1 = {"flower", "flow", "flight"};
        System.out.println("Test Case 1: " + solution.longestCommonPrefix(strs1)); // Expected output: "fl"
        
        String[] strs2 = {"dog", "racecar", "car"};
        System.out.println("Test Case 2: " + solution.longestCommonPrefix(strs2)); // Expected output: ""
    }
}

Time Complexity

This approach ensures efficient performance by progressively narrowing down the common prefix, checking only the necessary characters, and stopping early when a mismatch is found.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI