Problem Statement

Given an array of strings str, return the longest common prefix string amongst an array of strings. If there is no longest common prefix string exists, return an empty string.

Examples

• Example 1:

  • Input: strs = ["digital","dig","dinner"]
  • Expected Output: "di"
  • Justification: The strings share the initial fragment "di", but not beyond that. "dinner" diverges starting from the third character, making "di" the longest common prefix.

• Example 2:

  • Input: strs = ["happy","harbor","hard"]
  • Expected Output: "ha"
  • Justification: All strings start with "ha", but diverge afterwards. Hence, "ha" is the longest common prefix.

• Example 3:

  • Input: strs = ["apple","application","appetite", "app"]
  • Expected Output: "app"
  • Justification: The strings share the starting fragment "app", beyond which they start to differ. Therefore, "app" is identified as the longest common prefix.

Solution

To solve this problem, we'll employ a horizontal scanning technique. This involves comparing the first string with the rest of the strings in the array, one by one, to find the common prefix. This approach works well because it allows us to reduce the search space with each comparison. The logic behind this is that the longest common prefix of the array is no longer than the shortest string in the array. By incrementally adjusting the prefix as we traverse the array, we ensure an efficient and straightforward solution that is easy to implement.

In the beginning, we assume the entire first string to be the longest common prefix. Then, we iterate through the rest of the strings, shortening the assumed prefix from the end until it matches the start of the current string. This process is repeated until we've gone through all strings or the prefix is reduced to an empty string. This method is effective because it directly targets the problem's goal with minimal overhead, ensuring that we don't waste time checking unnecessary characters.

Step-by-step Algorithm

1. Initialize the Prefix: Start by assuming the first string in the array as the initial longest common prefix (lcp). This is because the longest common prefix, if any, cannot be longer than any string in the array.

2. Iterate Through Strings: Go through each string in the array one by one, starting from the second string, since the first string is already assumed as the lcp.

3. Compare and Adjust Prefix:

   • For each string, compare it with the current lcp from the beginning of the string.
   • If the current string starts with the lcp, move on to the next string in the array.
   • If the current string does not start with the lcp, reduce the lcp by removing characters from the end, one by one, until the current string starts with the lcp or the lcp becomes empty.
   • This step ensures that with each iteration, the lcp is adjusted to match the common starting sequence of all strings encountered so far.

4. Check for No Common Prefix: If at any point during the iteration, the lcp is reduced to an empty string, it means there is no common prefix among the strings. Return an empty string as the result.

5. Return the Longest Common Prefix: After iterating through all strings, the lcp at this point is the longest common prefix among all the strings in the array. Return the lcp as the result.

Algorithm Walkthrough

Let's consider the input ["apple","application","appetite", "app"].

1. Initialize the Prefix:

   • Assume lcp = "apple" as it is the first string in the array.

2. Iterate Through Strings:

   • The next string to compare with lcp is "application".

3. Compare and Adjust Prefix:

   • Comparison with "application":
     • Check if "application" starts with lcp ("apple").
     • "application" starts with "appl" but not "apple", so we need to adjust lcp.
     • Reduce lcp to "appl". Now, it matches.
     • Update lcp = "appl".

4. Move to Next String:

   • The next string to compare with lcp is "appetite".

5. Compare and Adjust Prefix:

   • Comparison with "appetite":
     • Check if "appetite" starts with lcp ("appl").
     • "appetite" starts with "app" but not "appl", so we need to adjust lcp.
     • Reduce lcp to "app". Now, it matches.
     • Update lcp = "app".

6. Move to Next String:

   • The next string to compare with lcp is "app".

7. Compare and Adjust Prefix:

   • Comparison with "app":
     • Check if "appetite" starts with lcp ("app").
     • "app" starts with "app", so lcp remains "app".

8. Return the Longest Common Prefix:

   • After comparing with all strings, lcp = "app" remains unchanged.
   • Return "app" as the longest common prefix.

Code

Complexity Analysis

• Time Complexity: The algorithm's time complexity is O(S), where S is the sum of all characters in all strings. In the worst case, we will compare all characters of all strings once.
• Space Complexity: The space complexity is O(1) since we only use a constant amount of space to store the lcp and iterate through the given strings.