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: strs = [ "flower ", "flow ", "flight "] Output: "fl "

Example 2:

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

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: strs(:)
    character(len=:), allocatable :: lcp

    strs = ["flower ", "flow ", "flight "]
    write(*,*) 'Example 1:'
    write(*,*) 'Input: ', strs
    write(*,*) 'Output: ', lcp(strs)

    strs = ["dog ", "racecar ", "car "]
    write(*,*) 'Example 2:'
    write(*,*) 'Input: ', strs
    write(*,*) 'Output: ', lcp(strs)

contains

    function lcp(strs) result(lcp_str)
        implicit none
        character(len=:), allocatable :: strs(:)
        character(len=:), allocatable :: lcp_str
        integer :: i, j, k
        logical :: found

        do i = 1, size(strs) - 1
            do j = i + 1, size(strs)
                if (strs(i)(1:1) == strs(j)(1:1)) then
                    found = .true.
                    do k = 2, min(size(strs(i)), size(strs(j)))
                        if (strs(i)(k:k) /= strs(j)(k:k)) then
                            found = .false.
                            exit
                        end if
                    end do
                    if (found) then
                        lcp_str = strs(i)(1:k-1)
                        return
                    end if
                end if
            end do
        end do
        lcp_str = ''
    end function lcp

end program main
❌ Compiled
❌ Executed
❌ Correct 
module longest_common_prefix

contains

  function longest_common_prefix(strs) result(prefix)
    implicit none
    character(len=*), intent(in) :: strs(:)
    integer :: i, j, k, l, m, n
    character(len=:), allocatable :: prefix

    ! Initialize the prefix to an empty string
    prefix = ""

    ! If there are no strings, return an empty string
    if (size(strs) == 0) then
      return
    end if

    ! Loop through each string and find the longest common prefix
    do i = 1, size(strs)
      ! Loop through each character in the current string
      do j = 1, len_trim(strs(i))
        ! If the current character is not the same as the previous character,
        ! break out of the loop
        if (j > 1 .and. strs(i)(j:j) /= strs(i)(j-1:j-1)) then
          exit
        end if

        ! If the current character is the same as the previous character,
        ! add it to the prefix
        if (j > 1 .and. strs(i)(j:j) == strs(i)(j-1:j-1)) then
          prefix = prefix // strs(i)(j:j)
        end if
      end do
    end do

  end function longest_common_prefix

end module longest_common_prefix

program main
  use longest_common_prefix
  implicit none
  character(len=*), parameter :: EXAMPLE_1 = "flower "
  character(len=*), parameter :: EXAMPLE_2 = "flow "
  character(len=*), parameter :: EXAMPLE_3 = "flight "
  character(len=*), parameter :: EXAMPLE_4 = "dog "
  character(len=*), parameter :: EXAMPLE_5 = "racecar "
  character(len=*), parameter :: EXAMPLE_6 = "car "
  character(len=*), parameter :: EXAMPLE_7 = "apple "
  character(len=*), parameter :: EXAMPLE_8 = "banana "
  character(len=*), parameter :: EXAMPLE_9 = "cherry "
  character(len=*), parameter :: EXAMPLE_10 = "dance "
  character(len=*), parameter :: EXAMPLE_11 = "sing "
  character(len=*), parameter :: EXAMPLE_12 = "dance "
  character(len=*), parameter :: EXAMPLE_13 = "sing "
  character(len=*), parameter :: EXAMPLE_14 = "dance "
  character(len=*), parameter :: EXAMPLE_15 = "sing "
  character(len=*), parameter :: EXAMPLE_16 = "dance "
  character(len=*), parameter :: EXAMPLE_17 = "sing "
  character(len=*), parameter :: EXAMPLE_18 = "dance "
  character(len=*), parameter :: EXAMPLE_19 = "sing "
  character(len=*), parameter :: EXAMPLE_20 = "dance "
  character(len=*), parameter :: EXAMPLE_21 = "sing "
  character(len=*), parameter :: EXAMPLE_22 = "dance "
  character(len=*), parameter :: EXAMPLE_23 = "sing "
  character(len=*), parameter :: EXAMPLE_24 = "dance "
  character(len=*), parameter :: EXAMPLE_25 = "sing "
  character(len=*), parameter :: EXAMPLE_26 = "dance "
  character(len=*), parameter :: EXAMPLE_27 = "sing "
  character(len=*), parameter :: EXAMPLE_28 = "dance "
  character(len=*), parameter :: EXAMPLE_29 = "sing "
  character(len=*), parameter :: EXAMPLE_30 = "dance "
  character(len=*), parameter :: EXAMPLE_31 = "sing "
  character(len=*), parameter :: EXAMPLE_32 = "dance "
  character(len=
🌐 Data from online sources 
def longest_common_prefix(strs):
    if not strs:
        return ""

    for i, c in enumerate(strs[0]):
        for j in range(1, len(strs)):
            if i == len(strs[j]) or strs[j][i] != c:
                return strs[0][:i]
    return strs[0]

The algorithm iterates through the characters in the first string and compares the equivalent characters in the subsequent strings. If there is a mismatch detected, return the common prefix up to the mismatch point. If the algorithm finishes iterating over the first string, return the entire first string as the common prefix.

  1. Check if the input array is empty, if it is, return an empty string as there is no common prefix.
  2. Iterate through the characters of the first string.
  3. For each character, iterate through the rest of the strings in the array.
  4. Compare the current character with the corresponding character in the other strings.
  5. If there is a mismatch or if we reach the end of a string, return the common prefix substring up to the current index.
  6. If the loop reaches the end of the first string, then the whole first string is the common prefix. Return the entire first string.
🌐 Data from online sources 
#include <vector>
#include <string>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";

    for (int i = 0; i < strs[0].size(); ++i) {
        char c = strs[0][i];
        for (int j = 1; j < strs.size(); ++j) {
            if (i == strs[j].size() || strs[j][i] != c) {
                return strs[0].substr(0, i);
            }
        }
    }
    return strs[0];
}

The algorithm iterates through the characters in the first string and compares the equivalent characters in the subsequent strings. If there is a mismatch detected, return the common prefix up to the mismatch point. If the algorithm finishes iterating over the first string, return the entire first string as the common prefix.

  1. Check if the input array is empty, if it is, return an empty string as there is no common prefix.
  2. Iterate through the characters of the first string.
  3. For each character, iterate through the rest of the strings in the array.
  4. Compare the current character with the corresponding character in the other strings.
  5. If there is a mismatch or if we reach the end of a string, return the common prefix substring up to the current index.
  6. If the loop reaches the end of the first string, then the whole first string is the common prefix. Return the entire first string.